最短路径问题数学模型

发布时间：2013-07-02 18:57:01 来源：文档文库

小中大

字号：

手机查看

问题重述：

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

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

D（0）=

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

D23(1)=min{d23(0),d21(0)+d13(0)}=min{2,3+∞}=2

D24(1)=min{d24(0),d21(0)+d14(0)}=min{∞,3+∞}=3

D25(1)=min{d25(0),d21(0)+d15(0)}=min{18,3+∞}=3

D26(1)=min{d26(0),d21(0)+d16(0)}=min{2.5,3+∞}=2.5

D27(1)=min{d27(0),d21(0)+d17(0)}=min{∞,3+∞}=3

D34(1)=min{d34(0),d31(0)+d14(0)}=min{6,∞+∞}=6

D35(1)=min{d35(0),d31(0)+d15(0)}=min{2,∞+∞}=2

D36(1)=min{d36(0),d31(0)+d16(0)}=min{∞,∞+∞}=∞

D37(1)=min{d37(0),d31(0)+d17(0)}=min{∞,∞+∞}=∞

D45(1)=min{d45(0),d41(0)+d15(0)}=min{3,∞+∞}=3

D46(1)=min{d46(0),d41(0)+d16(0)}=min{∞,∞+∞}=∞

D47(1)=min{d47(0),d41(0)+d17(0)}=min{∞,∞+∞}=∞

D56(1)=min{d56(0),d51(0)+d16(0)}=min{4,∞+∞}=4

D57(1)=min{d57(0),d51(0)+d17(0)}=min{∞,∞+∞}=∞

D67(1)=min{d67(0),d61(0)+d17(0)}=min{1.5,∞+∞}=1.5

由此可知

D（1）=,依次插入中间点v2,v3,v4,v5,v6,v7

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

D（2）=， D（3）=

D（4）=，D（5）=

D（6）=，D（7）=

求得距离矩阵D（7）的各元素值就是就是相应定点间的最短距离。

最后，计算第i行各元素值之和C（vi）即为vi 到其他个点的距离之和。由计算可得，v1到其他点的距离和为 C（v1）=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。比较可得，v2 到其他个点的距离最短，所以得，应将银行建在v2 点。