标号法求最短路径例题详解讲稿.ppt
关于标号法求最短路径例题详解第一页，讲稿共十页哦2标号法标号法(E.W.Dijkstra,1959)设带权图设带权图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第二页，讲稿共十页哦3标号法标号法(续续)1.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.算法算法:第三页，讲稿共十页哦4标号法求最短路径第一步：标号法求标号法求v0到到v5的最短路径的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 vir因为第一步因为第一步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。同理，因为通过同理，因为通过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 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第八页，讲稿共十页哦9 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同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束了，最后加一同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束了，最后加一行，把所有标红的数字重新写一遍，这些数字就是到达相应行，把所有标红的数字重新写一遍，这些数字就是到达相应vi所需要的最短路径所需要的最短路径第九页，讲稿共十页哦感感谢谢大大家家观观看看第十页，讲稿共十页哦
