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

文档介绍：最短路径带权图G=<V,E,w>,其中w:ER.eE,w(e)=(vi,vj),记w(e)=,vj不相邻,记wij=.设L是G中的一条路径,L的所有边的权之和称作L的权,记作w(L).u和v之间的最短路径:=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.*标号法(,1959)设带权图G=<V,E,w>,其中eE,w(e)={v1,v2,,vn},求v1到其余各顶点的最短路径p标号(永久性标号):第r步获得的v1到vi最短路径的权t标号(临时性标号):第r步获得的v1经过p标号顶点到达vi的路径的最小权,是v1到vi的最短路径的权的上界第r步通过集Pr={v|v在第r步已获得永久性标号}第r步未通过集Tr=V-Pr*标号法(续):=0,P0={v1},T0=V-{v1},vj(j=2,3,,n)获t标号:=,vi获得p标号:.令Pr=Pr-1{vi},Tr=Tr-1-{vi}.若Tr=,.vjTr,令令r=r+1,:*标号法求最短路径第一步:*标号法求v0到v5的最短路径v0v1v2v3v4v50014vir因为第一步v0只能够到达v1和v2,所以v1和v2下面写到达的权重,而v3~v5写无穷大。标号法求最短路径第二步:*标号法求v0到v5的最短路径v0v1v2v3v4v5001411/v0386vir因为第一步得到的数字当中除了已经确定的0以外,1最小,所以到达v1的最短路径确定了,为1,并且通过v0。因为通过v1到达v2需要3步,比4小,所以v2处写3。同理,因为通过v1到达v3和v4的权重和小于正无穷。标号法求最短路径第三步:*标号法求v0到v5的最短路径v0v1v2v3v4v5001411/v038623/v084vir因为第二步得到的数字当中3最小,v2最短为3。因为通过v2不能直接到达v3,所以v3下面还是8。通过v2到达v4需要4到达不了v5标号法求最短路径第四步: