《工程数学--最短路例题》由会员分享，可在线阅读，更多相关《工程数学--最短路例题（3页珍藏版）》请在金锄头文库上搜索。
1、1 求下图中从 V1点到其他任意一点的最短路（边旁的数字表示距离）：V2 6 V510 8 9 20V1 15 V3 2 V78 3 230V4 5 V6解： K=0，S=v1，= V2 , V3 , V4 ,V5 ,V6 ,V7 , l(v1)=0，l(vi)=,i=2,3,4,5,6,7SK=1，l(v2)=, 1122min ()(), ()l vw v vl v min010,10 类似地： l(v3)=15, l(v4)=8, l(vi)=，i=5,6,7。 ，4min ( )|min10,15,8,8()l vvSl v 所以 S=v1，v4，= V2 , V3 , V5 ,V6
2、,V7 , 所以 v1到 v4的最短路为 v1- S41()r vv v4， 距离为 8。K=2， 由于 v4与中 v3 ，v6 相邻，所以更新 v3 ，v6 的标号，得：Sl(v3)=,4433min ()(), ()l vw v vl v min83,1511 l(v6)=,4466min ()(), ()l vw v vl v min85,13 其他中的顶点标号不变。即：l(v2)=10，l(vi)=，i=5,7。S ，2min ( )|min10,11,13,10()l vvSl v 所以 S=v1，v4，v2，= V3 , V5 ,V6 ,V7 , 所以 v1到 v2的最短路为 v1
3、- S21()r vv v2， 距离为 10。K=3，由于 v2与中 v3 ，v5 相邻，所以更新 v3 ，v5 的标号，得：Sl(v3)=,2233min ()(), ()l vw v vl v min108,1111 l(v5)=,2255min ()(), ()l vw v vl v min106,16 其他中的顶点标号不变。即：l(v6)=13，l(v7)=。S ，3min ( )|min11,16,13,11()l vvSl v 所以 S=v1，v4，v2 ,v3，= V5 ,V6 ,V7 , S34()r vv 所以 v1到 v3的最短路为 v1- v4- v3(反向追踪 v3-
4、v4- v1) ，距离为 11。K=4，由于 v3与中 v5 ，v6 相邻，所以更新 v5 ，v6 的标号，得：Sl(v5)=,3355min ()(), ()l vw v vl v min119,1616 l(v6)=,3366min ()(), ()l vw v vl v min112,1313 其他中的顶点标号不变。即： l(v7)=。S ，6min ( )|min16,13,13()l vvSl v 所以 S=v1，v4，v2 ,v3 ,v6，= V5 ,V7 ,或, S64()r vv 63()r vv 所以 v1到 v6的最短路为 v1- v4- v6(反向追踪 v6- v4- v
5、1) ，距离为 13； 或 v1- v4- v3- v6(反向追踪 v6- v3- v4- v1) ，距离为 13K=5，由于 v6与中 v5 ，v7 相邻，所以更新 v5 ，v7 的标号，得：Sl(v5)=,6655min ()(), ()l vw v vl v min132,1615 l(v7)=,6677min ()(), ()l vw v vl v min1330,43 ，5min ( )|min15,4315()l vvSl v 所以 S=v1，v4，v2 ,v3 ,v6 ,v5，= V7 , S56()r vv 所以 v1到 v6的最短路为 v1- v4- v6- v5(反向追踪
6、v5- v6- v4- v1) ，距离为 15； 或 v1- v4- v3- v6- v5 (反向追踪 v5- v6- v3- v4- v1) ，距离为 15K=6，l(v7)= =。5577min ()(), ()l vw v vl v min1520,4335 所以 S= v1，v3，v2，v5，v4，v6，v7；所以 v1到 v7的最短路为 v1- v4- v6- v5- v7(反向追踪 v7- v5- v6- v4- v1) ，距离为 35；或 v1- v4- v3- v6- v5 - v7 (反向追踪 v7- v5- v6- v3- v4- v1) ，距离为 35v1到 其他点的最短路组成的树为：6V2 V510 8 9 20V1 15 V3 2 V78 3 215V4 5 V6或6V2 V510 8 9 20V1 15 V3 2 V78 3 215V4 5 V6
