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

1、关于标号法求最短路径例题详解第一张，PPT共十页，创作于2022年6月标号法(E.W.Dijkstra, 1959)设带权图G=, 其中eE, 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第二张，PPT共十页，创作于2022年6月2标号法(续)1. v1获p标号: =0, P0=v1, T0=V-v1, vj(j=2,3,

2、n)获t 标 号: =wij. 令r1.2. 设 , vi获得p标号: . 令 Pr=Pr-1vi, Tr=Tr-1-vi. 若Tr=, 则结束.3. vjTr, 令 令r=r+1, 转2.算法:第三张，PPT共十页，创作于2022年6月3标号法求最短路径第一步： 标号法求v0到v5的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 vir因为第一步v0只能够到达v1和v2，所以v1和v2下面写到达的权重，而v3v5写无穷大。第四张，PPT共十页，创作于2022年6月4标号法求最短路径第二步： 标号法求v0到v5的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1

3、/v0 3 8 6 vir因为第一步得到的数字当中除了已经确定的0以外，1最小，所以到达v1的最短路径确定了，为1，并且通过v0。因为通过v1到达v2需要3步，比4小，所以v2处写3。同理，因为通过v1到达v3和v4的权重和小于正无穷。第五张，PPT共十页，创作于2022年6月5标号法求最短路径第三步： 标号法求v0到v5的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 2 3/v0 8 4 vir因为第二步得到的数字当中3最小，v2最短为3。因为通过v2不能直接到达v3，所以v3下面还是8。通过v2到达v4需要4到达不了v5第六张，PPT共十页，创作于

4、2022年6月6标号法求最短路径第四步： 标号法求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 10vir第七张，PPT共十页，创作于2022年6月7标号法求最短路径第五步： 标号法求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 4 7/v4 9vir第八张，PPT共十页，创作于2022年6月8 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 4 8 6 2 4/v0 8 5 3 8 5/v2 6 4 8 6/v4 5 8/v1 w 0 1 4 8 5 6 =v0v1v2v4v3v5, w()=6vir同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束了，最后加一行，把所有标红的数字重新写一遍，