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

文档介绍：最短路径
带权图G=<V,E,w>, 其中w:ER.
eE, w(e)称作e的权. e=(vi,vj), 记w(e)=wij . 若vi,vj不
相邻, 记wij =.
设L是G中的一条路径, L的所有边的权之和称作L的
权, 记作w(L).
u和v之间的最短路径: u和v之间权最小的通路.
例1 L1=v0v1v3v5, w(L1)=10,
L2=v0v1v4v5, w(L2)=12,
L3=v0v2v4v5, w(L3)=11.
1
标号法(, 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
2
标号法(续)
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.
算法:
3
标号法求最短路径第一步:
4
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4 
vi
r
因为第一步v0只能够到达v1和v2,所以v1和v2下面写到达的权重,而v3~v5写无穷大。
标号法求最短路径第二步:
5
标号法求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的权重和小于正无穷。
标号法求最短路径第三步:
6
标号法求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
标号法求最短路径第四步:
7
标号法求v0到v5的最短路径
v0 v1 v2 v3 v4 v5
0 0 1 4 
1 1/v0 3 8 6 
2 3/v0 8 4 