最短路径问题数学模型

问题重述：

现准备在7 个居民点v 1, v 2, … , v7中设置一银行. 问设在哪个点, 最合理？要建2个银行呢？

解：先作出距离矩阵, 如下:

v1 v2 v3 v4 v5 v6 v7⎤⎡ ⎢ v1⎥ 0 3 ∞ ∞ ∞ ∞ ∞⎢⎥⎢ v2 3 0 2 ∞ 18 2.5 ∞⎥⎢⎥ v3 ∞ 2 0 6 2 ∞ ∞⎥ D （0）=⎢⎢ v4 ∞ ∞ 6 0 3 ∞ ∞⎥⎢⎥ v5 ∞ 18 2 3 0 4 ∞⎢⎥⎢ v6 ∞ 2.5 ∞ ∞ 4 0 1.5⎥⎢⎥ ∞ ∞ ∞ ∞ 1.5 0⎥⎢⎣ v7 ∞⎦

然后对k=1,2,3…,n 依次利用算法原理中第n 步递归公式，由已知的D n-1各元素确定D n 的各元素值。插入v 1后D （1）的个元素和相应的最短路径因为对成性，D （1）的第一行元素和第一列元素与D (0)相同，D （1）的主对角线上的元素均为0，所以只需要计算其余15个元素的值：

D 23(1)=min{d23(0),d 21(0)+d13(0)}=min{2,3+∞}=2

D 24(1)=min{d24(0),d 21(0)+d14(0)}=min{∞,3+∞}=3

D 25(1)=min{d25(0),d 21(0)+d15(0)}=min{18,3+∞

}=3

D 26(1)=min{d26(0),d 21(0)+d16(0)}=min{2.5,3+∞}=2.5

D 27(1)=min{d27(0),d 21(0)+d17(0)}=min{∞,3+∞}=3

D 34(1)=min{d34(0),d 31(0)+d14(0)}=min{6,∞+∞}=6

D 35(1)=min{d35(0),d 31(0)+d15(0)}=min{2,∞+∞}=2

D 36(1)=min{d36(0),d 31(0)+d16(0)}=min{∞, ∞+∞}=∞

D 37(1)=min{d37(0),d 31(0)+d17(0)}=min{∞, ∞+∞}=∞

D 45(1)=min{d45(0),d 41(0)+d15(0)}=min{3,∞+∞}=3

D 46(1)=min{d46(0),d 41(0)+d16(0)}=min{∞, ∞+∞}=∞

D 47(1)=min{d47(0),d 41(0)+d17(0)}=min{∞, ∞+∞}=∞

D 56(1)=min{d56(0),d 51(0)+d16(0)}=min{4,∞+∞}=4

D 57(1)=min{d57(0),d 51(0)+d17(0)}=min{∞, ∞+∞}=∞

D 67(1)=min{d67(0),d 61(0)+d17(0)}=min{1.5,∞+∞}=1.5

由此可知

⎡⎢0 3 ∞ ∞ ∞ ∞ ∞⎤

⎢3 0 2 3 3 2.5 3⎥

⎢∞ 2 0 6 2 ∞ ∞⎥⎥

D （1）=⎢⎢∞ 3 6 0 3 ∞ ∞⎥⎥, 依次插入中间点v 2,v 3,v 4,v 5,v 6, v 7

⎢⎢∞ 3 2 3 0 4 ∞⎥

⎢∞ 2.5 ∞ ∞ 4 0 1.5⎥

⎢⎥

⎣∞ 3 ∞ ∞ ∞ 1.5 0⎥⎦

可得不断更新的距离矩阵为：

3 5 6 6 5.5 6⎤3 5 6 6 5.5 6⎤⎡0 ⎡0 ⎢3 0 2 ⎥⎢3 0 2 ⎥3 3 2.5 33 3 2.5 3⎢⎥⎢⎥⎢5 2 0 ⎢5 2 0 5 2 4.5 5⎥5 2 4.5 5⎥⎥⎥（2）⎢（3）⎢D =⎢6 3 5 0 3 5.5 6⎥， D =⎢6 3 5 0 3 5.5 6⎥ ⎢6 ⎢6 3 2 3 0 4 6⎥3 2 3 0 4 6⎥⎢⎥⎢⎥5.5 2.5 4.5 5.5 4 0 1.55.5 2.5 4.5 5.5 4 0 1.5⎢⎥⎢⎥⎢6 ⎢6 3 5 6 6 1.5 0⎥3 5 6 6 1.5 0⎥⎣⎦⎣⎦

3 5 6 6 5.5 6⎤3 5 6 6 5.5 6⎤⎡0 ⎡0 ⎢3 0 2 ⎥⎢3 0 2 ⎥3 3 2.5 33 3 2.5 3⎢⎥⎢⎥⎢5 2 0 ⎢5 2 0 5 2 4.5 5⎥5 2 4.5 5⎥⎢⎥⎢⎥D （4）=⎢6 3 5 0 3 5.5 6⎥，D （5）=⎢6 3 5 0 3 5.5 6⎥ ⎢6 ⎢6 3 2 3 0 4 6⎥3 2 3 0 4 6⎥⎢⎥⎢⎥5.5 2.5 4.5 5.5 4 0 1.55.5 2.5 4.5 5.5 4 0 1.5⎢⎥⎢⎥⎢6 ⎢6 3 5 6 6 1.5 0⎥3 5 6 6 1.5 0⎥⎣⎦⎣⎦

3 5 6 6 5.5 6⎤3 5 6 6 5.5 6⎤⎡0 ⎡0 ⎢3 0 2 ⎥⎢3 0 2 ⎥3 3 2.5 33 3 2.5 3⎢⎥⎢⎥⎢5 2 0 ⎢5 2 0 5 2 4.5 5⎥5 2 4.5 5⎥⎢⎥⎢⎥D （6）=⎢6 3 5 0 3 5.5 6⎥，D （7）=⎢6 3 5 0 3 5.5 6⎥ ⎢6 ⎢6 3 2 3 0 4 6⎥3 2 3 0 4 6⎥⎢⎥⎢⎥5.5 2.5 4.5 5.5 4 0 1.55.5 2.5 4.5 5.5 4 0 1.5⎢⎥⎢⎥⎢6 ⎢6 3 5 6 6 1.5 0⎥3 5 6 6 1.5 0⎥⎣⎦⎣⎦求得距离矩阵D （7）的各元素值就是就是相应定点间的最短距离。最后，计算第i 行各元素值之和C （v i ）即为v i 到其他个点的距离之和。由计算可得，v 1到其他点的距离和为 C （v 1）=31.5，同理C(v2)=17.5, C(v3)=23.5, C(v4)=28.5, C(v5)=24, C(v6)=23.5, C(v7)=27.5。比较可得，v 2 到其他个点的距离最短，所以得，应将银行建在v 2 点。

若要建设两个银行，则可将银行地址选在v 2和 v 3 或 v 2 和 v 6 。