有向圖中任意令兩點(diǎn)之間的最短路徑

1、有向圖中任意兩點(diǎn)之間的最短路徑一. 問題求出有向圖中任意兩點(diǎn)之間的最短路徑并打印結(jié)果二. 語言環(huán)境c+三. 問題分析要解決有向圖中任意兩點(diǎn)之間的最短路徑問題首先應(yīng)解決的問題是1. 從源點(diǎn)到其余各點(diǎn)的最短路徑問題2. 每一對(duì)定點(diǎn)之間的最短路徑問題對(duì)于”從源點(diǎn)到其余各點(diǎn)的最短路徑問題” 有經(jīng)典算法-“迪杰斯特拉算法”.該算法的思想是: (1). 如圖（a）132113長度最短路徑81920164320 圖（a ）路徑長度最短的最短路徑的特點(diǎn)：在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 下一條路徑長度次短的最短路徑的特點(diǎn)：它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從

2、源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。再下一條路徑長度次短的最短路徑的特點(diǎn):它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。其余最短路徑的特點(diǎn)：它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。由以上特點(diǎn)可知：假設(shè)s為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為x）或者是弧（v,x)，或者是中間只經(jīng)過s中的頂點(diǎn)而最后到達(dá)終點(diǎn)x的路徑。 假設(shè)此路徑上有一個(gè)頂點(diǎn)不在s中，則說明存在一條終點(diǎn)不在s中，而長度比此路徑短的路徑

3、。但這是不可能的，因?yàn)槲覀兪前绰窂介L度遞增的次序來產(chǎn)生最短路徑的，故長度比此路徑短的所有路徑均已產(chǎn)生，他們的終點(diǎn)必定在s中，即假設(shè)不成立。設(shè)置輔助數(shù)組dist，其中每個(gè)分量distk 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。一般情況下，distk = 或者 = + 。（）在所有從原點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧即為第一條最短路徑(如圖(a )v0和k之間存在弧v0和k之間不存在弧其中的最小值即為最短路徑的長度。（）修改其它各頂點(diǎn)的distk值。假設(shè)求得最短路徑的頂點(diǎn)為u，若 distu+g.arcsukdistk則將 distk 改為 distu+g.arcsuk。迪杰斯特拉算

4、法程序段shortpath(mgraph g,int v0, int path, int dist)/pathv為從v0到v的最短路徑的前驅(qū)頂點(diǎn)，/distv為其當(dāng)前的最短距離.s為全局變量,sv=1,/表示v已在s集合中，即已求得從v0到v的最短距離。 for(v=0;vg.vexnum;+v) sv=0; distv=g.arcsv0v; if(distvinfinity) pathv=v0; /v0是v的前驅(qū) else pathv=-1; /v無前驅(qū) distv0=0; sv0=1; /s集中開始時(shí)只有v0 for(i=1;ig.vexnum;+i) min=infinity; for(

5、w=0;wg.vexnum;+w) if(sw=0) /wv-s if(distwmin) v=w; min=distw; sv=1; /將v加入s for(w=0;wg.vexnum;+w) /調(diào)整其余在v-s的點(diǎn) if(sw=0 &(distv+g.arcsvwdistw) distw= distv + g.arcsvw; pathw=v; v3v4v1v2v0v550 10 30 100 5 50 10 20 60 步驟第一步第二步第三步第四步第五步v1無v210（v0,v2）v360(v0,v2,v3）50(v0,v4,v3）v430（v0,v4）30（v0,v4）v5100（v0,v

6、5）100（v0,v5）90(v0,v4,v5)60(v0,v4,v3,v5)vjv2v4v3v5sv0,v2v0,v2,v4v0,v2,v4,v3v0,v2,v4,v3,v5對(duì)于” 每一對(duì)定點(diǎn)之間的最短路徑問題”有經(jīng)典算法弗洛伊德算法從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最短的路徑。若存在，則存在路徑vi,vj / 路徑中不含其它頂點(diǎn)若,存在，則存在路徑vi,v1,vj / 路徑中所含頂點(diǎn)序號(hào)不大于1若vi,v2, v2,vj存在， 則存在一條路徑vi, , v2, vj / 路徑中所含頂點(diǎn)序號(hào)不大于2 依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長度最

7、小者。cv316v10v223114abcv316v10v223114ab如圖（b） a b ca0 4 11 b 6 0 2c 3 0 圖（b ）實(shí)現(xiàn)任意兩點(diǎn)之間的最短路徑的計(jì)算和顯示可采用兩種實(shí)驗(yàn)方法：1. 先采用弗洛伊德算法計(jì)算出圖中所有結(jié)點(diǎn)之間的最短路徑，將最短路徑權(quán)值和最短路徑路徑分別存入相應(yīng)的數(shù)組中，然后用戶輸入所要查詢的兩點(diǎn)序號(hào)，直接便可查詢出最短路徑權(quán)值和最短路徑。2. 由迪杰斯特拉算法的思想，將所輸入的節(jié)點(diǎn)“v1” “v2”中任意一點(diǎn)作為源點(diǎn)，運(yùn)行迪杰斯特拉算法，當(dāng)求出“v1”“v2”之間的最短路徑之后就終止程序的運(yùn)行。(只用加入一個(gè)條件判斷語句就可實(shí)現(xiàn)) 程序如下因?yàn)榈谝环N

8、算法需要求出所有點(diǎn)之間的最短路徑,所以執(zhí)行效率較低,我采用第二種算法.四. 算法實(shí)現(xiàn)（程序）#include const int max=36727;/創(chuàng)建圖類 public class gint vexnum;/圖中的節(jié)點(diǎn)總數(shù) int arcsvexnum;/圖的帶權(quán)鄰接矩陣int distvexnum;/圖的最短路徑權(quán)值矩陣int pathvexnum;/用于記錄最短路徑的前驅(qū)頂點(diǎn)public g()/構(gòu)造函數(shù)vexnum=0;void initiatearcs(int vex) /帶權(quán)鄰接矩陣初始化vexnum= vex;for(int j=0; jvexnum; +j)for(int

9、k=0; kvexnum; +k)cin arcsjk;void shortpath(int v1,int v2 ) /求任意兩點(diǎn)之間的最短路徑/pathv為從v0到v的最短路徑的前驅(qū)頂點(diǎn)，/distv為其當(dāng)前的最短距離.s為全局變量,sv=1, /表示v已在s集合中，即已求得從v0到v的最短距離。for (v=0; vvexnum; +v) sv=0; distv=arcsv1v;if (distvinfinity) pathv=v0; /v0是v的前驅(qū)else pathv=-1; /v無前驅(qū)distv1=0; sv1=1; /s集中開始時(shí)只有v0for (i=1; ivexnum; +i)

10、 int min=max;for (int w=0; wvexnum; +w)if (sw=0) /wv-sif(distw min) v=w; min=distw; sv=1; /將v加入sfor(w=0;w vexnum; +w) /調(diào)整其余在v-s的點(diǎn)if(sw = 0 & (distv + arcsvw distw) distw= distv + arcsvw;pathw=v;if(v = v2) break;void printpath(int v1,int v2) /打印路徑cout pathv2 -;/運(yùn)用第歸 if (v1 != pathv2)printpath(v1,pathv2);void printresult ( int v1,int v2)cout the shortest path between v v1 and v v2 is:;printpath(v1,v2);cout the value of the shortest path is:;cout distv1v2 endl;main()/主函數(shù) g graph();int v1,v2;/用戶輸入任意兩點(diǎn)int vexnum;cout input vexnumber :;/輸入圖節(jié)點(diǎn)總數(shù)c