9.2最短更新 13 (k,),(1,y,确定这两条边的长度. 对网络进行如上处理后，即可在这个简化的网络上进行计算发点至到达点的最短路 径 四、有负边长网络的最短路 Dijkstra算法只适用于所有≥0的情形，当网络中有若干条负边权时，Dijkstra算 法就不能保证给出正确的结果了.例如图924所示 图924 用Dijkstra算法可求得：P()=0,P(2)=2,P()=1,而实际上1到的最短路 应该为12，长度为-2 在有负边长的网络上求最短路，网络中不能有长度为负数的回路，因为若有负回路 则可以在负回路上无限循环而使最短路无法球得.在有负边长的网络上求最短路时，必须 先检查是否满足这一要求 在有负边长的网络上求最短路可以用动态规划方法.但这里所用的动态规划方法与 第八章中所述方法有两点不同，一是由于问题的性质无法在计算前确定阶段数，二是采用 领序解法 在阶段k从始点到顶点巧的距离d4(,)为 de(v,vj)=minfdk-1(v,vi)+wijli =1,2,...,n} (9.1) 其中j=1,2,.,n 初始条件为d山(1，)=0 当对所有的j 12有d,)=4-1,线代路程收敛算法停止证 略).d4(心1，)即为始点至顶点巧的最短路长。 的8.以图9-24为例，按(9.1)式计算如下： k=1时： d(1,1)=11=0 d(1,2）=01,2-2 d1(1,3)=.3=1. 由于21和四1都是o心，所有以后各次线代d4,)=0,不再计算 k=2时： d2(m,t2）-min{d(,y)+.2b-1,2,3) =min{0+2.2+0.1+00}=2. d2(1,t)-min{d1(w1,)+e.3j-1,2,3} =mim0+1,2+(-4),1+0}=-2. §9.2 ù✌ú✌û✖ü✘ý 13 (vk, vy), (xl , vy), ➋✌✔✌➇✣ ➄✌✙æ✫✌✬. ✼➐❖P❏❧➛❀❵♦✤①, ✟✤❄✝➟✤➇❂ ➫◆✤æ➐❖P✤❀❏❧✤➬✤❤➣ ✠➁✤✡✝➜✠✤æ✭✤✮✝q ➆. ➠ ❩✥➡✧➢✧➤✧➥➧➦➩➨❞❝❜❭❞❫❞❴ Dijkstra ❤✌✐②✖✌❯s✌✒▲ wij ≥ 0 æ✁➫➉, ❙ ❖✘P ✕▲❽✁✽➄ ✔✙ ✚ ➩, Dijkstra ❤ ✐ ×✈ ➝✁➭✁➯➡✌❇✁➲✁➋æ✁❺➍ þ . ➳➛ ✑ 9–24 ✒ ✢ : ✑ 9–24 ❯ Dijkstra ❤✌✐❄✌☞✌②:P(v1) = 0,P(v2) = 2,P(v3) = 1, ➞✌③✌④✌❀ v1 ➵ v3 æ✭✌✮✁q ✽Ó ✻ v1v2v3, ✫✌✬✻ −2. ➟ ▲✝✔✙✤✫æ➐❖P✤❀☞✤✭✤✮✝q, ❖P ✕✈ ➝✤▲✫✤✬✻✝✔✤✛✤æ➺➸ q, ➌✤✻❽▲✝✔➺➸q, ❾✌❄✌❅✁➟✔❄➸q ❀✌❙✁➻✁➼✁➽✌➞✪✌✭✌✮✁q❙✌✐✁➾②. ➟ ▲✁✔✙✌✫æ✖❖✘P✌❀✁➾✭✌✮✁q✌➩, ✍✌✎ ➠✁➚✁➪❉ ➀✁➶✌➱✌➇✌❳✁➞➾ . ➟ ▲✝✔✙✤✫æ➐❖P✤❀✝➾✭✤✮✝q✤❄✤❅ ❯✝➹✝➘✓ ❀✤✯✤✐. t✤➇✝✏✤✒❯✤æ✝➹✝➘✓ ❀✤✯✤✐➈ í✁➴✁➷✖✕✘✒❁✌✯✌✐✌▲✌✣✁➬✈✁❈, ❳ ❉✖r s✁➮✁➱æ✁✃✁❐✌❙✌✐➟➬✌❤♠✁➋✌✔✁❒✁❮✛ , î❉●❯ ❰Ü❣ ✐ . ➟✁❒✁❮ k, Ï ⑤✁➬ v1 ➵➤✁➬ vj æ✦✌✧ dk(v1, vj ) ✻ : dk(v1, vj ) = min{dk−1(v1, vi) + wi,j |i = 1, 2, . . . , n} (9.1) ❊ ✕ j = 1, 2, . . . , n. ✬ ⑤➄✁➓✻ d1(v1, vj ) = w1j . ❙✼✁Ð✌▲✌æ j = 1, 2, . . . , n, ▲ dk(v1, vj ) = dk−1(v1, vj ), ÷✌❒✌ø✌Û✁Ñ✁Ò, ❤✌✐✌➚✌➪ (➯ ➇).dk(v1, vj ) ✟✻✌⑤✁➬ v1 ➁➤✁➬ vj æ✭✌✮✁q✌✫. õ 8. ❅✁Ó 9–24 ✻ ➳, ❲ (9.1) ❳✌➬✌❤➛é : k = 1➩: d1(v1, v1) = w1,1 = 0; d1(v1, v2) = w1,2 = 2; d1(v1, v3) = w1,3 = 1. r s w21 ❘ w31 ❈✌❉ ∞, Ð✌▲❅✌①✌✗✁❣÷✌❒ dk(v1, v1) = 0, ✈✌➻➬✌❤. k = 2➩: d2(v1, v2) = min{d1(v1, vj ) + wj,2|j = 1, 2, 3} = min{0 + 2, 2 + 0, 1 + ∞} = 2. d2(v1, v3) = min{d1(v1, vj ) + wj,3|j = 1, 2, 3} = min{0 + 1, 2 + (−4), 1 + 0} = −2