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

文档介绍：标号法(, 1959)
设带权图G=<V,E,w>, 其中eE, w(e)0.
设V={v1,v2,,vn}, 求v1到其余各顶点的最短路径
p标号(永久性标号) : 第r步获得的v1到vi最短路径的
权
t标号(临时性标号) : 第r步获得的v1经过p标号顶点
到达vi的路径的最小权, 是v1到vi的最短路径的权的上
界
第r步通过集Pr={v | v在第r步已获得永久性标号}
第r步未通过集Tr=V-Pr
*
标号法求最短路径例题详解
*
标号法(续)
1. v1获p标号: =0, P0={v1}, T0=V-{v1}, vj(j=2,3,,n)获t 标
号: =wij. 令r1.
2. 设 , vi获得p标号: .
令 Pr=Pr-1{vi}, Tr=Tr-1-{vi}.
若Tr=, 则结束.
3. vjTr, 令
令r=r+1, 转2.
算法:
*
标号法求最短路径例题详解
*
标号法求最短路径第一步：
*
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4   
vi
r
因为第一步v0只能够到达v1和v2，所以v1和v2下面写到达的权重，而v3~v5写无穷大。
标号法求最短路径例题详解
*
标号法求最短路径第二步：
*
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4   
1 1/v0 3 8 6 
vi
r
因为第一步得到的数字当中除了已经确定的0以外，1最小，所以到达v1的最短路径确定了，为1，并且通过v0。
因为通过v1到达v2需要3步，比4小，所以v2处写3。
同理，因为通过v1到达v3和v4的权重和小于正无穷。
标号法求最短路径例题详解
*
标号法求最短路径第三步：
*
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4  