思想：将D=（V，A，W）中v到所有其它顶点的最短路按其路长从小到大排列为：uo≤uj≤uz ≤...≤u,u,表示>到自身的长度，相应最短路记为：Po，P，P2，.….，Pn，P,一定只有一条弧。记X=，Xo=V\Xo，则ur = min wsiv,i Xo取最小值的点为V,:P,-P(vs，V)假定 uo，u，，u的值已求出，对应的最短路分别为 Pi-P(vs,Vi), P2=P(vs,V2), ..., Pk=P(vs,Vk)
思想：将D=（V，A，W）中vs到所有其它顶点的最短 路按其路长从小到大排列为： u0≤ u1 ≤ u2 ≤.≤ un u0表示vs到自身的长度，相应最短路记为： P0，P1，P2，.，Pn， 取最小值的点为v1 , ∴P1=P(vs , v1 ) 假定 u0，u1，.，uk的值已求出，对应的最短路分别 为 P1=P(vs ,v1 ), P2=P(vs ,v2 ), ., Pk=P(vs ,vk ) P1一定只有一条弧
记V, Xh=VIXX, = ,, Vi,V2...Vmin (u, + w(v,,v'))则Uk+1v,1 XkviXk使上式达到最小值的点可取为Vk+1°计算过程中可采用标号方法X中的点，u;值是V,到v,的最短路长度，相应的点记“永久”标号；PermanentX中的点，u,值是v,到v,的最短路长度的上界，相应的点记“临时"标号，供进一步计算使用。Temporary前点标号贝表示点v到v,的最短路上v;的前一点。如m，表示v,到v;的最短路上y,前一点是vm
记 则 使上式达到最小值的点v ’ 可取为vk+1。 计算过程中可采用标号方法。 Xk中的点，ui 值是vs 到vi 的最短路长度，相 应的点记“永久”标号； XK中的点，ui值是vs到vi的最短路长度的上界， 相应的点记“临时”标号，供进一步计算使用。 前点标号i : 表示点vs到vj的最短路上vj的前一点。 如i =m，表示vs到vj的最短路上vj前一点是vm。 Temporary Permanent
北京交通大学经济管理学院schng.stEcongounomics and Managomentrsin[3, v2][9, v.][5, v, ]V(4, vs)(10,v4) V-(0, VN4VSV4,v][0,v,]V6[9, vg][7, vs[8, vs]22Vs[4, v2]V[1, v,]8北京交通大学
北京交通大学经济管理学院图论第七章StingsEonguntnics and Managoment[3, V2]V.V-[9,va](6, r V4(4, v)[9, V.][4,V3][9, vg]VSV[7, v,]26V313, v2 17,vs[0, v,][9, vg][1, v, ]22[8, vs][4,v2] V5[4, v]北京交通大学
第七章 图论
北京交通大学图上标号法：经济管理学院SchoalsIofEcononnics and ManagomentJiaotong University1,001,6122186362N1,333V1.8V3?4N0100,042110V12VVV61, 81,81,1北京交通大学
1,6 图上标号法 : v v 5 2 2 3 4 6 4 v 3 v 1 v 4 1 2 10 6 1 2 10 v 8 v 9 v 7 2 6 3 3 v 6 0,0 1, ∞ 1,1 1, ∞ 1, ∞ 1, ∞ 1, ∞ 1,3