《最短路径问题数学模型》由会员分享，可在线阅读，更多相关《最短路径问题数学模型（3页珍藏版）》请在金锄头文库上搜索。
1、1问题问题重述：重述：现准备在 7 个居民点 v1, v2, , v7 中设置一银行.问设在哪个点, 最合理？要建2 个银行呢？解：先作出距离矩阵,如下:D（0）=0 1.5 v71.5 0 4 2.5 v6 4 0 3 2 18 v5 3 0 6 v4 2 6 0 2 v3 2.5 18 2 0 3 v2 3 0 v1v7 v6 v5 v4 v3 v2v1 然后对 k=1,2,3,n 依次利用算法原理中第 n 步递归公式，由已知的 Dn-1各元素确定 Dn的各元素值。插入 v1后 D（1）的个元素和相应的最短路径因为对成性，D（1）的第一行元素和第一列元素与D(0)相同，D（1）的主对角线上
2、的元素均为 0，所以只需要计算其余 15 个元素的值：D23(1)=mind23(0),d21(0)+d13(0)=min2,3+=2D24(1)=mind24(0),d21(0)+d14(0)=min,3+=3D25(1)=mind25(0),d21(0)+d15(0)=min18,3+=3D26(1)=mind26(0),d21(0)+d16(0)=min2.5,3+=2.52D27(1)=mind27(0),d21(0)+d17(0)=min,3+=3D34(1)=mind34(0),d31(0)+d14(0)=min6,+=6D35(1)=mind35(0),d31(0)+d15(0)
3、=min2,+=2D36(1)=mind36(0),d31(0)+d16(0)=min,+=D37(1)=mind37(0),d31(0)+d17(0)=min,+=D45(1)=mind45(0),d41(0)+d15(0)=min3,+=3D46(1)=mind46(0),d41(0)+d16(0)=min,+=D47(1)=mind47(0),d41(0)+d17(0)=min,+=D56(1)=mind56(0),d51(0)+d16(0)=min4,+=4D57(1)=mind57(0),d51(0)+d17(0)=min,+=D67(1)=mind67(0),d61(0)+d17(
4、0)=min1.5,+=1.5由此可知D（1）=,依次插入中间点 v2,v3,v4,v5,v6,v70 1.5 3 1.5 0 4 2.5 4 0 3 2 3 3 0 6 3 2 6 0 2 3 2.5 3 3 2 0 33 0可得不断更新的距离矩阵为：D（2）=， D（3）=0 1.5 6 6 5 3 61.5 0 4 5.5 4.5 2.5 5.56 4 0 3 2 3 66 5.5 3 0 5 3 65 4.5 2 5 0 2 53 2.5 3 3 2 0 36 5.5 6 6 5 3 030 1.5 6 6 5 3 61.5 0 4 5.5 4.5 2.5 5.56 4 0 3 2 3
5、 66 5.5 3 0 5 3 65 4.5 2 5 0 2 53 2.5 3 3 2 0 36 5.5 6 6 5 3 0D（4）=，D（5）=0 1.5 6 6 5 3 61.5 0 4 5.5 4.5 2.5 5.56 4 0 3 2 3 66 5.5 3 0 5 3 65 4.5 2 5 0 2 53 2.5 3 3 2 0 36 5.5 6 6 5 3 00 1.5 6 6 5 3 61.5 0 4 5.5 4.5 2.5 5.56 4 0 3 2 3 66 5.5 3 0 5 3 65 4.5 2 5 0 2 53 2.5 3 3 2 0 36 5.5 6 6 5 3 0D（6）=
6、，D（7）=0 1.5 6 6 5 3 61.5 0 4 5.5 4.5 2.5 5.56 4 0 3 2 3 66 5.5 3 0 5 3 65 4.5 2 5 0 2 53 2.5 3 3 2 0 36 5.5 6 6 5 3 00 1.5 6 6 5 3 61.5 0 4 5.5 4.5 2.5 5.56 4 0 3 2 3 66 5.5 3 0 5 3 65 4.5 2 5 0 2 53 2.5 3 3 2 0 36 5.5 6 6 5 3 04求得距离矩阵 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 点。若要建设两个银行，则可将银行地址选在 v2和 v3 或 v2 和 v6 。
