资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,最短路径,带权图,G,=,其中,w,:,E,R.,e,E,w,(,e,),称作,e,的,权,.,e,=(,v,i,v,j,),记,w,(,e,)=,w,ij,.,若,v,i,v,j,不,相邻,记,w,ij,=.,设,L,是,G,中的一条路径,L,的所有边的权之和称作,L,的,权,记作,w,(,L,).,u,和,v,之间的,最短路径,:,u,和,v,之间权最小的通路,.,例,1,L,1,=,v,0,v,1,v,3,v,5,w,(,L,1,)=10,L,2,=,v,0,v,1,v,4,v,5,w,(,L,2,)=12,L,3,=,v,0,v,2,v,4,v,5,w,(,L,3,)=11.,1,标号法,(E.W.Dijkstra, 1959),设带权图,G,=,其中,e,E,w,(,e,)0.,设,V,=,v,1,v,2,v,n,求,v,1,到其余各顶点的最短路径,p,标号,(,永久性标号,) :,第,r,步获得的,v,1,到,v,i,最短路径的,权,t,标号,(,临时性标号,) :,第,r,步获得的,v,1,经过,p,标号顶点,到达,v,i,的路径的最小权,是,v,1,到,v,i,的最短路径的权的上,界,第,r,步通过集,P,r,=,v,|,v,在第,r,步已获得永久性标号,第,r,步未通过集,T,r,=,V,-,P,r,2,标号法,(,续,),1.,v,1,获,p,标号,: =0,P,0,=,v,1,T,0,=,V,-,v,1,v,j,(,j=,2,3,n,),获,t,标,号,: =,w,ij,.,令,r,1.,2.,设,v,i,获得,p,标号,: .,令,P,r,=,P,r,-1,v,i,T,r,=,T,r,-1,-,v,i,.,若,T,r,=,则结束,.,3. ,v,j,T,r,令,令,r,=,r,+1,转,2.,算法,:,3,标号法求最短路径第一步：,4,标号法求,v,0,到,v,5,的最短路径,v,0,v,1,v,2,v,3,v,4,v,5,0,0,1 4, ,v,i,r,因为第一步,v0,只能够到达,v1,和,v2,，所以,v1,和,v2,下面写到达的权重，而,v3v5,写无穷大。,标号法求最短路径第二步：,5,标号法求,v,0,到,v,5,的最短路径,v,0,v,1,v,2,v,3,v,4,v,5,0,0,1 4, ,1,1/v0,3 8 6,v,i,r,因为第一步得到的数字当中除了已经确定的,0,以外，,1,最小，所以到达,v1,的最短路径确定了，为,1,，并且通过,v0,。,因为通过,v1,到达,v2,需要,3,步，比,4,小，所以,v2,处写,3,。,同理，因为通过,v1,到达,v3,和,v4,的权重和小于正无穷。,标号法求最短路径第三步：,6,标号法求,v,0,到,v,5,的最短路径,v,0,v,1,v,2,v,3,v,4,v,5,0,0,1 4, ,1,1/v0,3 8 6,2,3/v0,8,4,v,i,r,因为第二步得到的数字当中,3,最小，,v2,最短为,3,。,因为通过,v2,不能直接到达,v3,，所以,v3,下面还是,8,。,通过,v2,到达,v4,需要,4,到达不了,v5,标号法求最短路径第四步：,7,标号法求,v,0,到,v,5,的最短路径,v,0,v,1,v,2,v,3,v,4,v,5,0,0,1 4, ,1,1/v0,3 8 6,2,3/v0,8,4,3,7,4/v2,10,v,i,r,标号法求最短路径第五步：,8,标号法求,v,0,到,v,5,的最短路径,v,0,v,1,v,2,v,3,v,4,v,5,0,0,1 4, ,1,1/v0,3 8 6,2,3/v0,8,4,3,7,4/v2,10,4,7/v4,9,v,i,r,v,0,v,1,v,2,v,3,v,4,v,5,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,=,v,0,v,1,v,2,v,4,v,3,v,5,w,(,)=6,v,i,r,9,同理得到第五行，只是得到第五行以后所有都标红了，也就是所有都结束了，最后加一行，把所有标红的数字重新写一遍，这些数字就是到达相应,vi,所需要的最短路径,求,v,0,到,v,5,的最短路径,v,0,v,1,v,2,v,3,v,4,v,5,0,0,1 4, ,1,1,/,v,0,3 8 6,2,3,/,v,1,8 4,3 7,4,/,v,2,10,4,7,/,v,4,9,5,9,/,v,3,w,0 1 3 7 4 9,=,v,0,v,1,v,2,v,4,v,3,v,5,w,(,)=9,v,i,r,10,第六步：,
展开阅读全文