标号法求最短路径例题详解.ppt

文档介绍：关于标号法求最短路径例题详解
第1页，讲稿共10张，创作于星期二
*
标号法(, 1959)
设带权图G=<V,E,w>, 其中eE, w(e)0.
设V={v1,v2,,vn}, 求v1到其 4   
1 1/v0 3 8 6 
vi
r
因为第一步得到的数字当中除了已经确定的0以外，1最小，所以到达v1的最短路径确定了，为1，并且通过v0。
因为通过v1到达v2需要3步，比4小，所以v2处写3。
同理，因为通过v1到达v3和v4的权重和小于正无穷。
第5页，讲稿共10张，创作于星期二
*
标号法求最短路径第三步：
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4   
1 1/v0 3 8 6 
2 3/v0 8 4 
vi
r
因为第二步得到的数字当中3最小，v2最短为3。
因为通过v2不能直接到达v3，所以v3下面还是8。
通过v2到达v4需要4
到达不了v5
第6页，讲稿共10张，创作于星期二
*
标号法求最短路径第四步：
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4   
1 1/v0 3 8 6 
2 3/v0 8 4 
3 7 4/v2 10
vi
r
第7页，讲稿共10张，创作于星期二
*
标号法求最短路径第五步：
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5