中，…，y,∈Sn,y,是Sn，则w(H)=w(y,…,y,)+w,+1w(y,…,y)，由归纳假设， P(y,)=d(y,y)≤w(y,…,y,)，故w(H)=P(,)+w1+1w(y,…,y)。由算法知， P(y,)+w1≥Tn(y)≥Tn(y),故w(H)=T(y)+w(y,…,y)≥Tn(y)。因此，k=t1时结论也成立。 由归纳法知Dijkstra法是正确的。 对于赋权无向图G=(,E,W,边[y,V,]可视为两条弧(y,v)和(y,,),并且W,=",因此同样 可求出某点v,到每个点V,的最短链，算法类似于原算法。 无向图的Dijkstra法： 1.初始步。(P(y),(y》=(0,y),S={,},对每个y,∈八{y}, (Wsv,),[v,V ]EE (T(y,y,》= (co,M),[v,,v,]eE 令=0。 2.终止判别。若S=V，则停止，对每个y,∈V,d(y,y)=P(y,),并且用“反向跟踪”得到y,到 V,的最短链为： V,=(v)一V=(v)一。。一v2=(V)一V=(y,)-y 否则，转3。 3.确定永久标号。令T(g)=minT(v),则(P(,),2(:)》=(T(),(y,》,即将点y的临时标号改为 永久标号，S1=SUy}。 4.修改临时标号。考察每个[y,y,]∈E并且v,生S1的点y,若T(y,)>P(y,)+W,则令 (T(v),(v)=(P(y)+wy) 令k=k+1,转2。 例6.3.2书P264图10-19图上标出。 注6.3.1 dijkstra法只适用于所有w≥0的赋权图。当赋权图中存在负权时，则算法失效。如图10-20。 2.存在1"<0时的函数迭代法 对有向赋权图D=(V,A,W,不妨设任意两点y,y,∈V之间都有弧（如果在D中，(y,y)生A,则 添加弧(y,y,),并且W=+0） 利用如下结论：如P是D中从y,到v,的最短路，y,是P中的一个点，则从V,沿P到y,的路是D 中从V,到y,的最短路。设V={y,…,p},得到关系式： d(v,v,)=minfd(vs,v)+w,j=1.,p 函数迭代法： 对=1： d'(y,y)=wgj=1,…,p 对t2,3,:d'(y,y）=min{d-(y,y)+wg},j=1,…,p(记下最优解) >7 中 1, , r n v vS " ∈ ， l n v S ∉ ， 则 ( ) (, , ) (, ,) wH wv v w wv v = s " " r rl l i + + ，由归纳假设， () (, ) (, , ) Pv dv v wv v r sr s r = ≤ " ， 故 ( ) () (, ,) wH Pv w wv v = r rl l i + + " 。由算法知， () () () Pv w T v T v r rl n l n i +≥ ≥ ，故 ( ) () (, ,) () wH T v wv v T v = ni l i ni + ≥ " 。因此，k=n+1 时结论也成立。 由归纳法知 Dijkstra 法是正确的。 对于赋权无向图 G=(V,E,W)，边[, ] i j v v 可视为两条弧(, ) i j v v 和(,) j i v v ，并且 w w i j ji = ，因此同样 可求出某点 s v 到每个点 j v 的最短链，算法类似于原算法。 无向图的 Dijkstra 法： 1． 初始步。( ( ), ( )) (0, ) Pv v v s λ s s = ， 0 { }s S v = ，对每个 \{ } j s vVv ∈ ， ( , ), [ , ] ( ( ), ( )) ( , ), [ , ] sj s s j j j s j w v vv E Tv v M vv E λ ⎧⎪ ∈ = ⎨ ⎪ ∞ ∉ ⎩ 令 k=0。 2． 终止判别。若 k S V= ，则停止，对每个 j v V∈ ， (, ) () s j j dv v Pv = ，并且用“反向跟踪”得到 s v 到 j v 的最短链为： ( )l s j v v = λ — 1 ( ) l l j j v v λ − = — 。。。— 2 1 ( ) j j v v = λ — 1 ( ) j j v v = λ — j v 否则，转 3。 3． 确定永久标号。令 ( ) min ( ) j k i j v S Tv Tv ∉ = ，则( ( ), ( )) ( ( ), ( )) Pv v Tv v ii ii λ = λ ，即将点 i v 的临时标号改为 永久标号， 1 { } k ki S Sv + = ∪ 。 4． 修改临时标号。考察每个[, ] i j vv E ∈ 并且 j k 1 v S ∉ + 的点 j v ，若 ( ) () Tv Pv w j i ij > + ，则令 ( ( ), ( )) ( ( ) , ) Tv v Pv w v j j i ij i λ = + 令 k=k+1，转 2。 例 6.3.2 书 P264 图 10-19 图上标出。 注6.3.1 dijkstra法只适用于所有 0 wij ≥ 的赋权图。当赋权图中存在负权时，则算法失效。如图10-20。 2．存在 0 wij < 时的函数迭代法 对有向赋权图 D=(V,A,W)，不妨设任意两点 ,i j vv V∈ 之间都有弧（如果在 D 中，(, ) i j vv A ∉ ，则 添加弧(, ) i j v v ，并且 wij = +∞ ） 利用如下结论：如 P 是 D 中从 s v 到 j v 的最短路， i v 是 P 中的一个点，则从 s v 沿 P 到 i v 的路是 D 中从 s v 到 i v 的最短路。设 1 {, , } Vv v = " p ，得到关系式： ( , ) min{ ( , ) }, 1, , s j s i ij i dv v dv v w j p = += " 函数迭代法： 对 t=1： 1 ( , ) , 1, , s j sj dvv w j p = = " 对 t=2,3,…： 1 ( , ) min{ ( , ) }, 1, , t t s j s i ij i dvv d vv w j p − = += " （记下最优解）