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

《标号法求最短路径例题详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路径带权图G=,其中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之间权最小的通路.例1L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.1标号法(E.W.Dijkstra,1959)设带权图G=,其中eE,w(e)0.设V={v1,v2,,vn},求v1到其余各顶点的

2、最短路径p标号(永久性标号):第r步获得的v1到vi最短路径的权t标号(临时性标号):第r步获得的v1经过p标号顶点到达vi的路径的最小权,是v1到vi的最短路径的权的上界第r步通过集Pr={v

3、v在第r步已获得永久性标号}第r步未通过集Tr=V-Pr2标号法(续)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、一步：4标号法求v0到v5的最短路径v0v1v2v3v4v50014vir因为第一步v0只能够到达v1和v2，所以v1和v2下面写到达的权重，而v3~v5写无穷大。标号法求最短路径第二步：5标号法求v0到v5的最短路径v0v1v2v3v4v5001411/v0386vir因为第一步得到的数字当中除了已经确定的0以外，1最小，所以到达v1的最短路径确定了，为1，并且通过v0。因为通过v1到达v2需要3步，比4小，所以v2处写3。同理，因为通过v1到达v3和v4的权重和小于正无穷。标号法求最短路径第三步：6标号法求v0到v5的最短

5、路径v0v1v2v3v4v5001411/v038623/v084vir因为第二步得到的数字当中3最小，v2最短为3。因为通过v2不能直接到达v3，所以v3下面还是8。通过v2到达v4需要4到达不了v5标号法求最短路径第四步：7标号法求v0到v5的最短路径v0v1v2v3v4v5001411/v038623/v084374/v210vir标号法求最短路径第五步：8标号法求v0到v5的最短路径v0v1v2v3v4v5001411/v038623/v084374/v21047/v49virv0v1v2v3v4v50

6、01411/v048624/v085385/v26486/v458/v1w014856=v0v1v2v4v3v5,w()=6vir9同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束了，最后加一行，把所有标红的数字重新写一遍，这些数字就是到达相应vi所需要的最短路径求v0到v5的最短路径v0v1v2v3v4v5001411/v038623/v184374/v21047/v4959/v3w013749=v0v1v2v4v3v5,w()=9vir10第六步：