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

1、最短路径最短路径带权图带权图G=, 其中其中w:ER. 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标号法标号法(E.W.Dijkstra, 1959) )(ril

2、设带权图设带权图G=, 其中其中 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)(ril2标号法标号法(续续) )0(il1.

3、 v1获获p标号标号: =0, P0=v1, T0=V-v1, vj(j=2,3,n)获获t 标标 号号: =wij. 令令r1.2. 设设 , vi获得获得p标号标号: . 令令 Pr=Pr-1 vi, Tr=Tr-1-vi. 若若Tr=, 则结束则结束.3. vj Tr, 令令 令令r=r+1, 转转2.)1()( ririll)0(jlmin)1()1(1 rjTvrillrj,min)()1()(ijrirjrjwlll 算法算法: :3标号法求最短路径第一步：4 标号法求标号法求v0到到v5的最短路径的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 vir因为第一步因为

4、第一步v0只能够到达只能够到达v1和和v2，所以，所以v1和和v2下面写到达下面写到达的权重，而的权重，而v3v5写无穷大。写无穷大。标号法求最短路径第二步：5 标号法求标号法求v0到到v5的最短路径的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 vir因为第一步得到的数字当中除了已经确定的因为第一步得到的数字当中除了已经确定的0以外，以外，1最小，最小，所以到达所以到达v1的最短路径确定了，为的最短路径确定了，为1，并且通过，并且通过v0。因为通过因为通过v1到达到达v2需要需要3步，比步，比4小，所以小，所以v2处写处写3。同理，因为通过同理，因为

5、通过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 vir因为第二步得到的数字当中因为第二步得到的数字当中3最小，最小，v2最短为最短为3。因为通过因为通过v2不能直接到达不能直接到达v3，所以，所以v3下面还是下面还是8。通过通过v2到达到达v4需要需要4到达不了到达不了v5标号法求最短路径第四步：7 标号法求标号法求v0到到v5的最短路径的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4

6、 1 1/v0 3 8 6 2 3/v0 8 4 3 7 4/v2 10vir标号法求最短路径第五步：8 标号法求标号法求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 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( )=6vir9同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束了，最后加一行，把所有标红的数字重新写一遍，这些数字就是到达相应了，最后加一行，把所有标红的数字重新写一遍，这些数字就是到达相应vi所需要的最短路径所需要的最短路径求求v0到到v5的最短路径的最短路径 v0 v1 v2 v3 v4 v5 0