最短路径

8.4最短路径问题带权图：对于有向图或无向图的每条边附加一个实数w(e)，则得带权图。如果G1是带权图G的子图，称)()(1)E(Ge11GwGew，记作：的权为w(e)为边e上的权(当e=vi,vj时，权记作wij)，记作：G=V,E,W一、带权图及其最短路径问题G=V,E,W为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题。最短路径问题：如果v1v2…vn–1vn是v1到vn的最短路径，则v1v2…vn–1也必然是v1从到vn–1的最短路径。求最短路径的标号法的基本思想：标号法：(1)符号说明(i)li(r)*为顶点v1到顶点vi最短路径的权(ii)lj(r)为v1到vj最短路径权的上界，如果vj获得lj(r)，称vj在第r步获得t标号lj(r)(r0)如果顶点vi获得了标号li(r)*，称vi在第r步获得p标号li(r)*(iii)Pr={v|v已获得p标号}，称之为第r步通过集(r0)(iv)Tr=V–Pr称之为第r步未通过集(r0)二、求最短路径问题的标号法(2)算法：开始，r0，v1获p标号：l1(0)*=0，P0={v1}，T0=V–{v1}，vj(j1)的t标号：lj(0)=w1j=w1j0v1与vj相邻v1与vj不相邻修改通过集和未通过集：Pr=Pr–1∪{vi}，Tr=Tr–1∪{vi}，step1.求下一个p标号顶点设lj(r)*=min{lj(r–1)}，r1。vjTr–1顶点vi处，表明vi获得p标号。查Tr：若Tr=，则算法结束，否则转step2将lj(r)*标在相应step2.修改Tr中各顶点的t标号lj(r)=min{lj(r–1),li(r)*+wij}，li(r)*是刚刚获得p标号顶点的p标号。令rr+1，转step1。例8.7求下图中顶点v0与v5之间的最短路径v0v2v1v4v3v5121475326解：利用标号法算法解此题开始，r0，v0获p标号：l0(0)*=0l1(0)=w01=1通过集P0={v0}，未通过集T0={v1，v2，v3，v4，v5}，l2(0)=w02=4l4(0)==l5(0)l3(0)=w03=未通过集的t标号：v0v2v1v4v3v5121475326第一步：r=1，计算=l1(1)*=1，所以i=1，P1={v0,v1}，T1={v2,v3,v4,v5}修改未通过集的t标号：l2(1)=min{l2(0),l1(1)*+w12}=min{4,3}=3l3(1)=min{l3(0),l1(1)*+w13}=min{,8}=8l4(1)=min{l4(0),l1(1)*+w14}=6l5(1)=min{l5(0),l1(1)*+w15}=}{min)0(0jvlTjvi获p标号l1(1)*，修改通过集与未通过集:修改通过集与未通过集P2={v0,v1,v2}，T2={v3,v4,v5}修改未通过集的t标号：l3(2)=min{l3(1),l2(2)*+w23}=min{8,3+}=8l4(2)=min{l4(1),l2(2)*+w24}=min{6,3+1}=4l5(2)=min{l5(0),l2(2)*+w25}=min{,3+}=，，，计算第二步23}{min2)1(2(1)jTv1jillr3)*2(22lpv标号获修改通过集与未通过集P3={v0,v1,v2,v4},T3={v5,v3}修改未通过集的t标号：l3(3)=min{l3(2),l4(3)*+w43}=min{8,4+3}=7l5(3)=min{l5(2),l4(3)*+w45}=min{,4+6}=10，，所以，计算第三步44}{min3)2(4(2)jTv2jillr4)*3(44lpv标号获修改通过集与未通过集P4={v0,v1,v2,v4,v3},T4={v5}修改未通过集的t标号：l5(4)=min{l5(3),l3(4)*+w35}=min{10,7+2}=9，，所以，计算第四步37}{min4)3(3(3)jTv3jillr7*)4(33lpv标号：获修改通过集与未通过集P5={v0,v1,v2,v4,v3,v5},T5=由于T5=，过程结束，得v0到v5的最短路径为：=v0,v1,v2,v4,v3,v5，且w()=9，，所以，计算第五步59}{min5)4(5(4)jTv4jillr9)*5(55lpv标号：获标号法的说明：(1)标号法可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“开始”步中，先给顶点Vs加p标号0，即ls(0)*=0，然后算法往下计算。(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。