1、最短路徑算法及應用乘汽車旅行的人總希望找出到目的地的盡可能的 短的行程。如果有一張地圖并在圖上標出每對十字路口 之間的距離，如何找出這一最短行程？一種可能的方法就是枚舉出所有路徑，并計算出每 條路徑的長度，然后選擇最短的一條。那么我們很容易 看到，即使不考慮包含回路的路徑，依然存在數以百萬 計的行車路線，而其中絕大多數是不值得考慮的。在這一章中，我們將闡明如何有效地解決這類問 題。在最短路徑問題中，給出的是一有向加權圖G = （V， E，可），其中V為頂點集，E為有向邊集，W為邊上 的權集。最短路徑問題研究的問題主要有：單源最短路 徑問題、與所有頂點對之間的最短路徑問題。一、單源最短路徑問題所

2、謂單源最短路徑問題是指：巳知圖G= （V，E）， 我們希望找出從某給定的源結點SeV到V中的每個結 點的最短路徑。首先，我們可以發(fā)現有這樣一個事實：如果P是G 中從vs到vj的最短路，vi是P中的一個點，那么，從 vs沿P到vi的路是從vs到vi的最短路。（一）Dijkstra算法對于圖G，如果所有Wij0的情形下，目前公認的 最好的方法是由Dijkstra于1959年提出來的。例1巳知如下圖所示的單行線交通網，每弧旁的 數字表示通過這條單行線所需要的費用，現在某人要從 vi出發(fā)，通過這個交通網到v8去，求使總費用最小的 旅行路線。Dijkstra方法的基本思想是從vs出發(fā)，逐步地向外 探尋最

3、短路。執(zhí)行過程中，與每個點對應，記錄下一個 數(稱為這個點的標號)，它或者表示從vs到該點的最短 路的權(稱為P標號)、或者是從vs到該點的最短路的 權的上界(稱為T標號)，方法的每一步是去修改T標號， 并且把某一個具T標號的改變?yōu)榫逷標號的點，從而 使G中具P標號的頂點數多一個，這樣至多經過n-1(n 為圖G的頂點數)步，就可以求出從vs到各點的最短路。在敘述Dijkstra方法的具體步驟之前，以例1為例 說明一下這個方法的基本思想。例1中，s=1。因為所 有Wij0故有d(v1, v1)=0。這時，v1是具P標號的 點。現在考察從v1發(fā)出的三條弧，(v1, v2), (v1, v3) 和(

4、v1, v4)。如果某人從v1出發(fā)沿(v1, v2)到達v2，這 時需要d(v1, v1)+w12=6單位的費用；如果他從v1出 發(fā)沿(v1, v3)到達v3,這時需要d(v1, v1)+w13=3單位 的費用；類似地，若沿(v1, v4)到達v4，這時需要d(v 1, v1)+w14=1 單位的費用。因為 min d(v1, v1)+w12, d(v1, v1)+w13，d(v1, v1)+w14= d(v1, v1)+w14=1， 可以斷言，他從v1到v4所需要的最小費用必定是1 單位，即從v1到v4的最短路是(v1, v4)，d(v1, v4)=1。 這是因為從v1到v4的任一條路？，如

5、果不是(v1, v4)， 則必是先從v1沿(v1, v2)到達v2,或者沿(v1, v3)到達 v3。但如上所說，這時他巳需要6單位或3單位的費用 ，不管他如何再從v2或從v3到達v4,所需要的總費 用都不會比1小(因為所有wij0)o因而推知d(v1, v4) =1,這樣就可以使v4變成具P標號的點。現在考察從 v1及v4指向其余點的弧，由上巳知，從v1出發(fā)，分 別沿(v1, v2)、(v1, v3)到達v2, v3,需要的費用分別 為6與3，而從v4出發(fā)沿(v4, v6)到達v6所需的費用 是 d(v1, v4)+w46=1+10=11 單位。因 min d(v1, v1) +w12, d

6、(v1, v1)+w13, d(v1, v4)+w46= d(v1, v1)+ w13=3o基于同樣的理由可以斷言，從v1到v3的最短 路是(v1, v3), d(v1, v3)=3。這樣又可以使點v3變成 具P標號的點，如此重復這個過程，可以求出從v1到 任一點的最短路。在下述的Dijstra方法具體步驟中，用P, T分別表 示某個點的P標號、T標號，si表示第i步時，具P標 號點的集合。為了在求出從vs到各點的距離的同時， 也求出從Vs到各點的最短路，給每個點v以一個入值， 算法終止時A(v)=m，表示在Vs到v的最短路上，v的 前一個點是Vm；如果X(v)=8，表示圖G中不含從Vs 到

7、v 的路；A(Vs)=0o Dijstra方法的具體步驟：初始化0S0=Vs, P(Vs)=0 A(Vs)=0對每一個 vVs，令 T(v)=+ 8, A(v)=+ 8,k=s開始如果Si=V，算法終止，這時，每個vSi, d(V s,v)=P(v)；否則轉入考察每個使(Vk,vj)eE且vj Si的點vj。如果 T(vj)P(vk)+wkj,則把T(vj)修改為 P(vk)+wk j,把A(vj)修改為k。令戲)=牌頃七)如果戲七) +B，則把七的標號變?yōu)镻標號p=戲),令京=泌%) , k=ji, i=i+1，轉，否 則終止，這時對每一個veSi, d(vs,v)=P(v),而對每一 個

8、v 畢涕d(%v) = T(y)。算法實現:1、數據結構大用鄰接矩陣表示圖G大 用一維數組DI存放從源點到I點的最短路徑 長度或其上界。（上面算法中的P標號與T標號實際 上存放著源點到某點的最短路徑長度或其上界，因此我 們可以統(tǒng)一用D數組來表示）。大 用一維數組？，其中PI記錄到I點的最短路 徑中前一個頂點的序號。$R+2、源程序Program Min_Road_Dijkstra;Const MaxN=100;Type GraphType=Array1. . MaxNj 1. . MaxN of integer; 有向圖鄰接矩陣Varw:GraphType;圖&結構? Wl, j表不:頂點i到

9、j之間的費用s., n:integer;M為源點，ii為圖G的頂點數存放M源點到任意頂點之間的最短路徑長度或其上界D:array1. MasNofinteger;SS:array 1. . MaxN ofboolean;標有 F標號的頂點集合(pi存放最短路中頂點1的前面頂點編號 p:array1. . Maxnofinteger;Procedure Init; 文件輸入過程，讀入圖信息 var f :test;k, y, nw, i, j： integer;beginassign(f., miniroadRoad. inJ );reset (f);readln(f., n3 s_, nw);

10、for i：=l to n dofor j：=1 to n dowi., j ：=Maxint;for i：=l to nw doreadln (f, k, y_, w k., y);close (f);end;Procedure Dijkstra; Dijkstra法過程var miiij k., ij j_, tempk： integer;beginfillchar(SS sizeof(S耽 0);：+=t=t=+=+=+=+=t始化：+=+=+=+=t=+=+=+=+=t=t：)SSs : =true ;ps ：=0; t點標上 P 標號for i：=l to n doif is the

11、n D i ：=ws., i;Ds ：=0;k：=s;min：=-l;：+=+=t=t=+=+=+=+=M=+=+=+=t=t=+=+=+=+=M=+=+=+=t=t：while mmOMaxint do 當存在所有T標號點的距離上界的最小值beginmin：=Maxint;for j ： = 1 to n do begin在所有T標號點進行操作如果J未標F標號，且到J的路徑長度上界可更新，則更新為較小值if (not ss j) and(wk, j OMasint) and(dj D k+k_, j) then begin Dj:=Dk-hfk,.;pj ：=k；end;尋找最小具有T標號的

12、距離最小點if (not ss j)and(DjCmin) then beginmin：=Dj;TempK：=j;end;end;if jninMasint then begin 如果找到，則該點標上F標號 k：=tempk;ss k： = true;end;end;end;Procedure Print; 打印出路徑var i_, j : integer;temps., temppath： string;beginfor i：=l to n doif is thenif D i=Maxint then 如果D 二Maxint,則輸出無路徑到該點 wiitelnfs.,J ToJ j 5 ha

13、ve no pathJ )else begin 否則從該點倒著輸出M源點到該點的路徑wiitelnfsjJ To J j i,J Cost ：JD i);temppath：=J;str (i_, temps);temppath：=J +t emp s+t empp ath;j：=pi；while j0 do beginstr (j., temps);temppath：=一涎 +temps+temppath;J：=pj；end;str (s_, temps);temppath:二 temps+temppath;wiiteln(temppath);end;end;timgin 主程序init;Di

14、jkstra;print;end.(二)Bellman-Ford 算法在單源最短路徑問題的某些實例中，可能存在權為 負的邊。如果圖G=(V, E)不包含從源s可達的負 權回明 則對所有vev,最短路徑的權定義d(s,v)依然 正確，即使它是一個負值也是如此。但如果存在一從s 可達的負回路，最短路徑的權的定義就不能成立。S到 該回路上的結點就不存在最短路徑。當有向圖中出現負 權時，則Dijkstra算法失效。當不存在源s可達的負回 路時，我們可用Bellman-Ford算法實現。下面我們介紹有向圖中，存在具有負權的弧時，求 最短路的方法。為了方便起見，不妨設從任一點vi到任一點vj都 有一條弧（

15、如果在Gk ,（vi,vj）不存在，則添加（vi,vj）且令 wij=+8）。顯然，從vs到vj的最短路總是從vs出發(fā)，沿著一 條路到某個點vi,再沿（vi,vj）到vj的（這里vi可以是v s本身），由本章開始時介紹的一個結論可知，從vs 到vi的這條路必定是從vs到vi的最短路，所以d（vs,v i）必滿足如下方程：（弋，%） =mjn為了求得這個方程的解盼（這里 P為圖G中的頂點數目），可用如下遞推公式：開始時，令舟 S%）=改（J = 12.）對 t=2,3,.,= mm 似1（、叫）+嗎 （j = 12.是）若進行到某一步，例如第k步時，對所有j=12.,p,有：八”七）=小*方則（

16、叫心次即為VS到各點的最短路的權。不難證明：（1）如果G是不含回路的賦權有向圖，那么，從 VS到任一個點的最短路必可取為初等路，從而最多包 含P2個中間點；（2）上述遞推公式中的 八叫是在至多包含t-1 個中間點的限制條件下，從vs到vj的最短路的權。由（1）（2）可知：當G中不含負回路時，上述 算法最多經過p-1次迭代必定收斂，即對所有的j=1,2,., P,均有西&舟5），從而求出從VS到各個頂點 的最短路的權。如果經過p-1次迭代，存在某個j,使，則說明G中包含有負回路。顯然， 這時從vs到vj的路是沒有下界的。根據以上分析，Bellman-Ford算法可描述為：For j：=1 to

17、n doIf jS thenDj：=Ws,.ElseDj：=O;K：=0;RepeatK：=K+1;Change：=False;For j：=1 to n doIf thenFor i：=l to n doIf j OMaxint) and(D l OMaxint) and(D j D ll+urEl, j) then beginDj：= Dl-hrl, j;Change：=true;End;Until (not Change)or(k=n-l);算法實現1、數據結構（同Dijkstra算法，略）2、源程序$R+Prograjn Min_Road_ Be 1 lman_ Ford;Const

18、MasN=100;Type GraphType=Array1. . MaxN, 1. . MaxNof integer;VarwGxaphType;s, ninteger;Darray1. . MaxNof integer;Parray1. . Maxnof integer;Changeboolean;Procedure Init;var f :test;x, y, nw, i, j： integer;beginassignffj minir o adRo adl. in5);reset (f);readlnff,烏 s., nw);for i：=l to n dofor j：=1 to n

19、dow i., j ：=Maxint;for i：=l to nw doreadln (f_,毛 y_, w k., y);close (f);end;Procedure Ford; Bellman_f ord法過程var miiij k., i3 j, tempk： integer;beginps ：=0;for i：=l to n doif is then D i ：=ws., i;Ds ：=0;K：=0;RepeatK：=K+1;Change：=False;For j：=1 to n doIf jS thenFor i：=l to n doIf (wl, j OMasint) and(D

20、 l OMaxint) and(D j D IJ+titEI., j) thenbeginDj：= Dl-hl, j;Change：=true;Pj： = i；end;Until (not Change)or(k=n-l);end;Procedure Print;var i_, j : integer;temps., temppath： string;beginfor i：=l to n doif is thenif Di=Maxint thenvrriteln(s.,5 ToJ i,3 have no path!)else beginwiitelntsj5 To J, i,J Cost:JD

21、 i);temppath：=J;str (i., temps);temppath： =J +temps+temppath;j：=pi；while j0 do begin str (j_, temps);temppath： =J 一! +temps+temppath;j：=pj；end;str (s_, temps);t empp ath: = t emp s+t empp ath;writeln(temppath);end;end;beginmaininit;ford;print;readln;end.(三)有向無回路圖中的單源最短路徑若圖G是一個無回路有向圖，求圖G的單源最短 路徑問題可以在

22、O(V+E)時間內計算出單源最短路徑。 在有向無回路圖中最短路徑總是存在的，這是因為即使 圖中有權為負的邊，也不可能存在權為負的回路。算法開始時先對有向無回路圖進行拓樸排序，以便 獲得結點的線性序列。如果從結點u到結點v存在一通 路，則在拓撲序列中u先于v。在拓撲排序過程中我們 僅對結點執(zhí)行一趟操作。當對每個結點進行處理時，從 該結點出發(fā)的所有邊也被松馳。算法描述如下：Procedure Dag_Shortest_ Paths (G, w, s);Begin對G的結點進行拓撲排序for I：=l to n do begind口PINILendDs0for拓撲序列中的每個結點u dofor vE

23、 Adj u doif dvu頓(u, v) then begind v - d u頓(u, v)Pvuendend二、每對結點間的最短路徑我們要討論找出圖中每對結點間最短路徑問題。這 個問題在實踐中常常會出現。例如，對一公路圖，要造 表說明其上的每對城市間的距離時就可能出現這種問 題。對于有向圖G(V，E，可)，要求每對結點間的 最短路徑，我們可以把單源最短路徑算法運行IV I次 來解決，每次依序把圖中的每個結點作為源點。如果所 有邊的權為非負，可以采用Dijkstra算法，算法的運行 時間為O (V3)；如果允許有負權邊的存在，我們必 須對每個結點運行一次速度較慢的Bellman-Ford

24、算 法，其中運行時間為O (V2E)，對稠密圖則為O (V 4)。下面我們介紹一種動態(tài)程序設計方案來解決可以 存在負權邊但無負回路的有向圖G=(V, E),每對 結點間的最短路徑問題，所產生的算法稱為Floyd-War shall算法，其運行時間為O (V3)。最短路徑的結構在Floyd-Warshall算法中，考察的是一條最短路徑 上的中間結點，其中某條簡單路徑P= 的中間結點是P中除V1和Vj以外的任何結點，即任 何屬于集合V2,V3.,Vj 1的結點。該算法主要基于下列觀察。設G的結點為V= 1, 2,.,n，并對某個k考察其結點子集1,2, .,k。 對任意一對結點i,ju V,考察從

25、i到j且其中間結點皆屬 于集合1,2, .,k的所有路徑，設P是其中一條最小 權路徑（因為我們假定G中不包含負權回路，所以P 是簡單路徑）。Floyd-Warshall算法利用了路徑P與從 i到j間的最短路徑（所有中間結點皆屬于集合1,2, ., k-1之間的聯(lián)系。這一聯(lián)系取決于k是否是路徑p的 一個中間結點。如果k是路徑p的中間結點，由如下圖所示，我們 把p分解為p1 （M） ,p2皿頃）。由前面可知，p1是 從i到k的一條最短路徑，且其所有中間結構均屬于集 合1,2, .,k。事實上，結點k不是路徑pl的中間結點，所以pl 是從i到k的一條最短路徑，且滿足所有中間結點均屬 于1,2, .,

26、k-1。類似地，p2是從k到j的一條最短 路徑，且其中間結點皆屬于集合1,2, .,k-1。（二）解決每對結點間最短路徑問題的一種遞歸方 案基于上述觀察，我們將給出定義最短路徑估計的一 個遞歸公式。設端 為從結點i到結點j且滿足所有中 間均屬于集合1,2, .,k的一條最短路徑的權。當k =0時，從結點i到結點j的路徑中根本不存在中間結點， 因此它至多包含一條邊，則有聰=改，遞歸定義由下 式給出：若mmS尸】息尸+站T）若止小矩陣給出了最后解，對所有的i,jV成立因為 其所有中間點皆屬于1,2, .,n。腫=（吧（三）自底向上計算最短路徑的權基于以上給出的遞歸定義，我們可以運用下面自底 向上過

27、程按k值的遞增順序計算職。過程的輸入是n* n的矩陣可。其返回值關于最短路徑的權的矩陣。Floyd-Warshll（W）1 nrowW2for k-l to ndo for id i_, k +d k_, j thenbegindi,. ：= di, k+dk, j;Pi, j：=k；End;End;根據矩陣？，要計算出頂點i到j的最短路徑可以由以下過程Path(i,j)實現：Procedure Path(i,j:integer);Var k:integer;BeginK:=Pi,j;If k=0 then return;Path(i,k);Print(k);Path(k,j);End;源程序

28、Const MaxN=50;Type Arrtype=array1.MaxN, 1. . MaxNof integer;var i_, n： integer;p:array1. . MaxN, 1. . MasNof integer;d, w：Arrtype;f :test;Procedure Floyd(Var D：Arrtype;W：Arrtype);Vax i, j, k：integer;beginfor i：=l to n dofor j：=1 to n dobegindi, j ：=wi, j；Pi,.：=0；End;for k：=l to n dofor i：=l to n dof

29、or j：=1 to n doif (di, k OMaxint) and(dk., j OMaxint) and(di, j di_, k +dk_, j) then begindi, j ：= di, k+dk, j;Pi,.j：=k；End;End;Procedure Path(i_, j : integer);Var k：integer;BeginK：=Pi, j；If k=0 then esit;Path(i,k);JJ LPath(k, j);End;Procedure init;var f：text;i, t, m, y, im： integer;beginassign(f mi

30、niroadroad. inlJ);reset (f);readln(f _,烏 t_, im);for i：=l to n dofor j：=1 to n doif i= j then wi, j ：=0 else wi., j ：=Masint;for i：=l to wn doreadln (f ., x, y., w k_, y);close (f); end;begininit;f loydfd, w);assign (f_, miniroadroad. outJ );rewrite(f);for i：=l to n dofor j：=1 to n doifand(di_, j OMaxint) thenbeginwritein (f, Path to 3 3 j/ ：Jdi, j)write (f., i3 3 一一J) ;path(i, j) ;writeln(f, j);end;readln;close(f);end.三、應用舉例1、設備更新問題。某企業(yè)使用一臺設備，在每年 年初，企業(yè)領導部門就要決定是購置新的，還是繼續(xù)使 用舊的。若購置新設備，就要支付一定的購置費用；若 繼續(xù)使用