1第五章圖論與網(wǎng)絡(luò)優(yōu)化2§5-1引論§5-2圖論基本概念

§5-3樹及其優(yōu)化問題§5-4最短路問題3三、有向圖最短路算法

1964年，F(xiàn)ord提出了可求解含負權(quán)的最短路問題的遞推標號法。

設(shè)賦權(quán)有向圖D=(V,A,W)，V中含p個點，現(xiàn)要求始點v1至終點vp的最短路Rp*及其路長rp*。假定D中無負回路（其上總權(quán)為負數(shù)的回路），將原弧集A增廣為新弧集，以使V中任意兩點間均有互為反向的兩條弧，同時權(quán)集W增廣為新權(quán)集。于是，原圖D增廣為新圖。4

其中，當(dāng)i=j時，若設(shè)，則與實際背景不符，若<0，則出現(xiàn)負回路，故須定義為0。由Bellman最優(yōu)化原理易知：從v1到vj的最短路長rj*必滿足,反之亦然。

顯見，若某兩相鄰點之間有多于一條的同向弧，則可棄大留小，簡化為一條弧，從而是一個完全的二重賦權(quán)有向圖，其中，增廣的權(quán)集，定義為：5基本思路：首先設(shè)任一點vi到任一點vj都有一條弧，如果在圖G中，(vi,vj)?A，則添加弧(vi,vj)，并令wij=+

。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點vi，再沿弧(vi,vj)到vj

。則v1到vi的這條路必然也是v1到vi的最短路。否則，從v1到vj的這條路將不是最短的。于是，設(shè)rj表示從v1到vj的最短路長，ri表示從v1到vi的最短路長，則有下列方程：6利用如下的遞推公式：

開始時，令

即用v1到vj的直接距離做初始解。

從第二步起，使用遞推公式：

求

當(dāng)進行到第t

步，若出現(xiàn)：則停止計算。

即為v1到各點的最短路長。7計算步驟：Step1.

初始標號Step2.

第k+1次標號Step3.

當(dāng)成立

時，即得

從vp出發(fā)，反向追蹤，確定最短路Rp*。若Rp*中vj已確定，按式確定前一點vi；否則，k:=k+1，轉(zhuǎn)Step2。最后得到的標號就是v1到各點vi（i=1,2,…,p）的最短路長。8

因已知圖中頂點為p個，故算法至多經(jīng)(p–2)+1=p–1次迭代必收斂。若一旦出現(xiàn)：則說明D中必含負回路。在負回路上每循環(huán)一次，路長減少一個定值，永無休止，最終導(dǎo)致：【例5】求圖5-9中從v1到v8的最短路。圖5-9v1v2v6v3v4v51-2v7v87-3-1683-3-5-1-1211-529解：利用上面的遞推公式，將計算結(jié)果列出，如下表所示(空格為+∞)

：

終點始點v1v2v3v4v5v6v7v8v10-1-23v2602v3-30-51v4802v5-10-3v61017v7-10-5v800-1-230-5-2-71-150-5-2-7-3-1-5-20-5-2-7-3-1-5-100-5-2-7-3-1-5-10v1v2v6v3v4v51-2v7v87-3-1683-3-5-1-1211-5210可以看出，當(dāng)t=4時，有：

因此，表中的最后一列，就是從v1到v2，….，v8的最短路權(quán)。

從v8出發(fā)，反向追蹤，確定最短路R8*。

于是得一條最短路R8*={v1,v3,v4,v7,v8}，路長為r8*=-10。

上述計算過程，不僅求得了兩個定點之間的最短路，而且同時得到一個定點至其他各點的最短路。至于求各點對之間的最短路，則可重復(fù)應(yīng)用上述計算法來解決。v1v2v3v4v5v6v7v801234R8*v10-1-23100000*v26022-1-5-5-5-5v3-30-513-2-2-2-2-2*v480243-7-7-7-7*v5-10-351-3-3-3v610176-1-1-1-1v7-1075-5-5-5*v8-508-2-10-10*完整的計算表如下所示(表中沒有數(shù)字的空格表示+∞)。11四、無向圖最短路算法

設(shè)非負賦權(quán)簡單圖G=(V,E,W)，V中含p個點，求始點v1至終點vp的最短路及其路長。

這里，介紹一種固定標號法（Dijkstra法）。其要點是對點vi(i≠1)用兩種標號：先用臨時標號ti(是v1到vi最短路長的某個上界)，再用固定標號ri(是v1到vi的最短路長)。作一次迭代，就將至少一個ti點變?yōu)閞i點（又稱“將未著色點著色”）。至多經(jīng)p–1次迭代，vp變?yōu)閞p*點，于是得到v1至vp的最短路長，再反向追蹤，定出最短路。計算過程中，以Vt表示ti點集，Vt中元素將由多變少，直至成為空集。12Dijkstra算法的計算步驟如下：Step1.始點v1作固定標號r1*=0，其余點vj作臨時標號tj=∞，Vt={v2,v3,…,vp}。Step2.設(shè)當(dāng)前已得到一個或多個vi的固定標號ri*，對vj∈N(vi)∩Vt，修改vj的臨時標號為：其中，右端的tj是原值，左端的tj是修改值。

Step3.對vj∈Vt，取：為對應(yīng)點vj*的固定標號，Vt:=Vt-｛vj*｝。Step4.當(dāng)Vt=Φ時，得rp*，再從vp出發(fā)，反向追蹤，確定最短路Rp*。若Rp*中vj已確定，按式，確定前一點vi；否則，轉(zhuǎn)Step2。13Dijkstra算法示例：求v1到v6的最短路+∞+∞+∞+∞+∞（1）首先給v1以r標號，r(v1)＝0，給其余所有點T標號，T(vj)＝＋∞（j=2，3，…6)(0)

r標號以（）形式標在結(jié)點旁邊，T標號以不帶（）的數(shù)字標在結(jié)點旁邊

.v6v5v3v1v4v2365112436

實際上，所有點最后得到的固定標號正是v1到各點的最短路路長。用于有向圖時，只要取vj∈N+(vi)∩Vt即可。14r(v2)=3

（3）5r(v3)=4

（4）+∞+∞v6v5v3v1v4v2365112436+∞+∞+∞(0)9（2）考察

v1:

T(v2)=min[T(v2)，r(v1)+a12]＝min[∞，0＋3]=3T(v3)=min[T(v3)，r

(v1)+a13]＝min[∞，0＋5]=5所以，r

(v2)=

3（3）考察

v2:T(v3)=min[T(v3)，r(

v2)+a23]＝min[5，3＋1]=4T(v4)=min[T(v4)，r(v2)+a24]＝min[∞，3＋6]=9所以，r(v3)=4T(v3)=5

T(v4)=9

15r(v5)=5（3）（4）v6v5v3v1v4v2365112436+∞+∞(0)9（5）T(v4)=8

（4）考察

v3:

T(v5)=min[T(v5)，r(v3)+a35]＝min[∞，4＋1]=5T(v4)=min[T(v4)，r(v3)+a34]＝min[9，4＋4]=8所以，r(v5)=

5（5）考察

v5:T(v6)=min[T(v6)，r(v5)+a56]＝min[∞，5＋6]=11T(v4)=min[T(v4)，r(v5)+a54]＝min[8，5＋2]=7所以，r(v4)=

7

8T(v6)=11

11（7）r(v4)=7

16（3）（4）v6v5v3v1v4v236511243611(0)（5）（7）（6）考察

v4:T(v6)=min[T(v6)，r(v4)+a46]＝min[11，7＋3]=10所以，r(v6)=10所有點都標上r標號．

r(v6)=10(10)17(7)標出最短路

v1到v6的最短路可從v1開始，根據(jù)永久性標號數(shù)值回溯得到．最短路徑是：v1→v2→v3→v5→v4→v6，路長10．同時得到至其余各點的最短路，即各點的永久性標號r（vi）．

注意：

雙標號法只適用于所有wij

≥0的情形，當(dāng)賦權(quán)有向圖中存在負權(quán)時，則算法失效．

（3）（4）v6v5v3v1v4v2365112436(0)（5）（7）(10)18

由以上計算過程可知，每迭代一次，固定標號個數(shù)就會增加。作第k+1次迭代時，在第k次迭代時才取得固定標號的點之各鄰點的臨時標號重又查視一遍，有的得以保留，而有的可能改進。最后，在當(dāng)前所有臨時標號中取出最小值，其對應(yīng)的點就作為新增加的固定標號點。當(dāng)然，一個最小值可對應(yīng)多個點，從而，一次迭代有可能同時得到多個固定標號點，總迭代次數(shù)不超過p-1。19

【例7】求圖5-11所示圖中從v1至v8的最短路及路長。V1V2V3V4V5V6V7V8281671422934962圖5-1120【解】計算表如下：

01234567R8*v1*v2*v3*v4v5*v6*v7v8*V1V2V3V4V5V6V7V82816714229349