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

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

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

4、 v4)。如果某人從v1出發沿(v1, v2)到達v2, 這時需要d(v1, v1)+w12=6單位的費用；如果他從v1出發沿(v1, v3)到達v3，這時需要d(v1, v1)+w13=3單位的費用；類似地，若沿 (v1, v4)到達v4，這時需要d(v1, 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 o這是因為從v1到v4的任一條路P,如果不是(v1

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

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

7、。Dijstra 方法的具體步驟：初始化i=0S0=Vs , P(Vs)=0 入(Vs)=0對每一個 vVs，令 T(v)=+ g,入(v)=+ g, k=s 開始 如果Si=V，算法終止，這時，每個v Si, d(Vs,v)=P(v);否則轉入 考察每個使(Vk,vj) E且vj Si的點vj。如果 T(vj)P(vk)+wkj ，則把 T(vj)修改為 P(vk)+wkj，把 入(vj)修改為 k。叫=霜) 令如果V .的標號變為PP標號,k=ji , i=i+1，轉，否則終止，這時對每一個v Si, d(vs,v)=P(v),算法實現:1、數據結構衣 用鄰接矩陣表示圖 G* 用一維數組D

8、l存放從源點到I點的最短路徑長度或其上界。（上面算法中的P標號與T標號實際上存放著源點到某點的最短路徑長度或其上界，因此我們可以統一用D數組來表示）。* 用一維數組P,其中Pl記錄到I點的最短路徑中前一個頂點的序號。$R+2、源程序Program Min_Road.lDi_ikstra;Const MaxN=100;Type Gr aphTyp b=Air ay 1. ” MaxNj 1. * MaxN of integer,有向圖鄰接距陣Vaiw:GxaphType;圖G結構i Wl. 表示頂點i到j之間的費用s, n:integer;s兩源點j n溝圖G的頂點數存啟從源點到任意頂點之間的最

9、短路徑長度或其上界D:airayl,ofinteger;SS:airayl. .NIaxNlofboolean；標肓 P 標號的頂點集合p i存戰最短路中頂點i的前面頂點編號p:axrayl.ofinteger;Procedure Init; 文件輸入過程！讀入圖信息Jvar f :text；弧兀 rw, ljj：integer;beinassign(fj,J miniroadRoad, inJ);reset (f)；r eadln (f . n. s, nw);fi：=l tc n dofor j:=1 to n dow i. ： =Maxint; far i：=l to nw doread

10、ln (f_, k., y, w z., y),close(f)；end;Procedure Dijkstra; Dijkstza 算法過程Tar iiin* k, i, j* teuipk: integer;beginfillchar (SSf sizenf (SS)jO);樣口和*1初始化柑*M=M=M=M=SSs ：=true;ps ： =0; 源點標上 P 標號for i;-l to n doif is then Di:=wst i,Ds ：=0,min：-1;while minOMaxint do 當存在所有 T標號點的距離上界的最小E【beginiain：=Maxint;for j

11、：=l o n do begin 在所有T標號點進行操作如果j未標P標號，且到的路徑長度上界可更新，則更新為較小值 if (not ss j)and(vk3 jNaaint)and(djk+vk, j) then begin Dj：=D k+vk, j;P【j炷;end,尋找最小具有T標號的距離最小點.if (not ss j) and(D jthen beginmin：=Dj;TanpK：=j;end;end;if minOlaxint then bein 找到3 則該點標上 P 標號kztenpkss k : = true;end;end;end;Procedure Print, 打印出路

12、徑var i., j：inte?ei;temps., temppath：string;beinfor iE to n doif iOs thanif D i=Maxint then 如果D I =Maxint)則輸出無路徑到該點writhave no path!)else beain否則從該點倒著輸出從源點到該點的路徑)writelnCsj? To iCwt： . D i);tempp ath;3 ;str Cij, temps);t empp ath ：=，一一 J +t emp s+t empp ath;j：=pil；while j0 do beginstr (jj, temps);tem

13、ppath： +1 emp s+t empp ath,j=P 山end;ctr(碼 temps);t empp ath：=tejnp s+temppath.；writeln (temppath);end;end；主程序init;Dijkstra;print;end.(二) Bellma n-Ford 算法在單源最短路徑問題的某些實例中，可能存在權為負的邊。如果圖G=(V,日不包含從源s可達的負權回路，則對所有v V,最短路徑的權定義d(s,v)依然正確，即使它是一個負值也是如此。但如果存在一從s可達的負回路，最短路徑的權的定義就不能成立。S到該回路上的結點就不存在最短路徑。當有向圖中出現負權時

14、，貝UDijkstra算法失效。當不存在源s可達的負回路時，我們可用Bellman-Ford算法實現。下面我們介紹有向圖中，存在具有負權的弧時，求最短路的方法。為了方便起見，不妨設從任一點vi到任一點vj都有一條弧(如果在 Gk ,(vi,vj) 不存在，則添加(vi,vj) 且令wij=+ x)。顯然，從vs到vj的最短路總是從 vs出發，沿著一條路到某個點 vi，再沿(vi,vj) 到 vj的(這里vi可以是vs本身)，由本章開始時介紹的一個結論可知，從vs到vi的這條路必定是從vs到vi的最短路，所以d(vs,vi)必滿足如下方程：= 川少”巧)討為了求得這個方程的解-m（這里P為圖G中

15、的頂點數目），可用如下遞推公式：開始時，令沙（耳丹）=吟（廠12加對 t=2,3,習叭叫旳）=呼 3円厲出）+% （j = 1Z若進行到某一步，例如第k步時，對所有j=1,2,.,p, 有：則即為vs到各點的最短路的權。不難證明：（1） 如果G是不含回路的賦權有向圖，那么，從vs到任一個點的最短路必可取為初等 路，從而最多包含 P 2個中間點；& （v V（2） 上述遞推公式中的-是在至多包含t-1個中間點的限制條件下，從 vs 到vj的最短路的權。由（1） （ 2）可知：當G中不含負回路時，上述算法最多經過p-1次迭代必定收斂，即對所有的j=1,2,.,P, 均有，從而求出從vs到各個頂點的

16、最短路的權。V ）工耳 Vj ）如果經過p-1次迭代，存在某個j，使，則說明G中包含有負回路。顯然，這時從vs到vj的路是沒有下界的。根據以上分析，Bellma n-Ford算法可描述為：For j：=l to n doIfthenDj：=Ws, jElseDj：=O;K:=0;RepeatK：-K+l;Change：=False;For j：=1 to n doIfthenFor 1:=1 to n doIf (譏I, j加血訕!:)and(DI Maxirrt) and(D j Dl+w i, j) then beinDj：= Dtrl-hFj；Change ： =true;End;Unt

17、il (not Change)or(k=nl):算法實現1、數據結構(同Dijkstra 算法，略)2、源程序$R+Prcgram Mi n_ Road .Bel lnian F or d;Const NlaxN=100;Type Gr aphTyp e=Air ay1. ”MaxN* 1.MskMof integer;Varw:GraphType;n :integer;D:irxay1. KaNofinteger;p:array1. Maxnofinteger;Change:boolean,Procedure Init;var fext；龍,眄 1, j： integer;beginassi

18、gn(fj mmir adRoadl in)；reset(f);readln (f_, n3 勺 nw);far i：=1 to n dofor j：=l to n dovi j :-MaxzLnt;for iE to nw doreadln(f . x, yt vx, y)；close(f);end;Procedure Ford; Bsllman. faid算法過程var minj k, i, j, teinpk： integer;beginps ：=0;for i:=l to n doif is then D i :=vs_, i；Dk ：=0;K：=0;RepeatK：=K+1;Chan

19、ge：=False;For j：=1 to n doIf jQS thenFor i：=l to n doIf Cvl, j Mllaxint) and CD i MUaxint) and (D j D l+wI? j ) then beginChanged true;Pj ：=i；end;Until (not Change)ar(k=n-l);end;Procedure Print;vax i? j:integer,temps., temppath： stxing;beginfox i：二1 to n doif is thenif D1=MaKint thenritelntsj, ?To i

20、jJ have no path!)else beginwritelnfs,1 To J j ih J Cost/ , D i);temppath：=，J ;str (i_, temps),tenippath：=，+tenips_Hteiiippath;while jOO do begin str (j,. temps);temppath：=J +t emp s+t empp a th;J：=pj；end;str (斗 temps);tenppath = temp s+t eniippathwritein (temppath);end;end;begin jaain)zLnit; fold, p

21、rint; xeadln;end.(三) 有向無回路圖中的單源最短路徑若圖G是一個無回路有向圖，求圖G的單源最短路徑問題可以在O(V+E)時間內計算出單源最短路徑。在有向無回路圖中最短路徑總是存在的，這是因為即使圖中有權為負的邊， 也不可能存在權為負的回路。算法開始時先對有向無回路圖進行拓樸排序，以便獲得結點的線性序列。如果從結點u到結點v存在一通路，則在拓撲序列中u先于v。在拓撲排序過程中我們僅對結點執行一趟操作。當對每個結點進行處理時，從該結點出發的所有邊也被松馳。算法描述如下：Froceduze Dag_Shortest_Paths(G vr3 s); Begin對G的結點進行拓撲拉序f

22、or I：=1 to n do beginPI-HILendDs-0for拓撲序列中的每個結點.u dofor Adj u doif dtvjdfuj-hrtu, v) then begin d *d u -hr 仏 v)Pbd jendend二、每對結點間的最短路徑我們要討論找出圖中每對結點間最短路徑問題。這個問題在實踐中常常會出現。例如， 對一公路圖，要造表說明其上的每對城市間的距離時就可能出現這種問題。對于有向圖G(V，E, W，要求每對結點間的最短路徑，我們可以把單源最短路徑算 法運行丨V|次來解決，每次依序把圖中的每個結點作為源點。如果所有邊的權為非負，可 以采用Dijkstra算法

23、，算法的運行時間為O ( V3);如果允許有負權邊的存在，我們必須對每個結點運行一次速度較慢的Bellman-Ford算法，其中運行時間為 O(V2E)，對稠密圖則為0( V4)。下面我們介紹一種動態程序設計方案來解決可以存在負權邊但無負回路的有向圖G=(V, E),每對結點間的最短路徑問題，所產生的算法稱為Floyd-Warshall算法，其運行時間為O (V3)。(一) 最短路徑的結構在Floyd-Warshall算法中，考察的是一條最短路徑上的中間結點，其中某條簡單路徑P=的中間結點是P中除V1和Vj以外的任何結點，即任何屬于集合V2,V3,Vj 1 的結點。該算法主要基于下列觀察。設G

24、的結點為V= 1,2，,n，并對某個k考察其結點子集 1,2，,k 。對任意一對結點i,j V,考察從i到j且其中間結點皆屬于集合1,2，,k 的所有路徑，設P是其中一條最小權路徑(因為我們假定 G中不包含負權回路，所以P是簡單路徑)。Floyd-Warshall算法利用了路徑 P與從i到j間的最短路徑(所有中間結點皆屬于集合1,2，,k-1之間的聯系。這一聯系取決于k是否是路徑p的一個中間結點。如果k是路徑p的中間結點，由如下圖所示，我們把 p分解為pl （廠k） ,p2 （kj ）。由前面可知，pl是從i到k的一條最短路徑，且其所有中間結構均屬于集合1,2，,k o事實上，結點k不是路徑p

25、l的中間結點，所以pl是從i到k的一條最短路徑，且滿足 所有中間結點均屬于1,2，,k-1。類似地，p2是從k到j的一條最短路徑，且其中間結點皆屬于集合1,2，,k-1 o（二）解決每對結點間最短路徑問題的一種遞歸方案基于上述觀察，我們將給出定義最短路徑估計的一個遞歸公式。設1為從結點i到結點j且滿足所有中間均屬于集合1,2，,k 的一條最短路徑的權。當k=0時，從結點押）=i到結點j的路徑中根本不存在中間結點，因此它至多包含一條邊，則有山,遞歸定義由下式給出：算（碼巴笛斜+廿“）若疋=C1若疋2 1矩陣給出了最后解，對所有的i,j V成立一一因為其所有中間點皆屬于1,2，,n o（三）自底向

26、上計算最短路徑的權基于以上給出的遞歸定義，我們可以運用下面自底向上過程按k值的遞增順序計算n*n的矩陣W其返回值關于最短路徑的權的矩陣。Floyd-VfarshllW1 nerowM22 for k-1 to n3 do for i-l to n4 do for jdiflk+dk, j thenbegindij j：= dti.kl+dtkj, j;End,End,根據矩陣P,要計算出頂點i到j的最短路徑可以由以下過程Path(i,j) 實現：Procedure Path(i,j:i nteger);Var k:i nteger;Begi nK:=Pi,j;If k=0 the n retu

27、r n;Path(i,k);Prin t(k);Path(k,j);End;(五) 源程序Const MaxN=50;Type Airtype=array 1* . MaxN, 1* . MaxNof integer;var , n： integei;p： airayl, MaxN, L. + MaxN of integei 7df 世：Arrtype;f :text;Procedure Floyd(Var D：Arrtype;V： AxrtypeJ TVar if B k：integer；beginfor ir=l to n dofor j:=1 to n dobegind 九 j:=wi.

28、 j;PL,i：=O;End;for k:=l to n dofor i:-l to n dofor j：=l to n doif (di, kJOMaxintJandtdtk. jlOMaxiiitJand Cdti, j di, k+dk, then beindit j ：= dti.ekl+dtk, j;P 也 jk;End;End;Procedure Fathfi, j:integer);Var k：integer;BeginK：=Pi, jl；If k=O then exit;Path(i,k);write (f,k/J);Path(k, j);End,Procedure init;

29、var f:text;i, J, t, x, y, wn： integer;beginassign (f, miniroadr ad. ini);xeet (f);readln(f t n, t., wn);for i:=1 to n dofor j：=l to n doi=j then wi, j ： =0 else wi, j Maxint;for i： =1 ta im doxeadln(f, Xj y_, w x_, y);close (f);end;begininit;f loydfd, w);assign (f * jainiroadroad outJ);rewrite Of);for i：=l to n dofor j：=1 to n doif (iXj) and (d i_. j Maxint) thenbeginwriteln(f/Pathto ：di j);write (f,t i,J _J) ;path(irl j) ;writeln(f,);end;readln;close (f);end.三、應用舉例1、設備更新問題。某企業使用一臺設備，在每年年初，企業領導部門就要決定是購置 新的，還是繼續使用舊的。若購置新設備，就要支付一定的購置費用；若繼續使用舊設備， 則需支付一定的維修