1、第四章第三節(jié) 最短路徑算法 如下圖所示，我們把邊帶有權(quán)值的圖稱為帶權(quán)圖。邊的權(quán)值可以理解為兩點(diǎn)之間的距離。一張圖中任意兩點(diǎn)間會(huì)有不同的路徑相連。最短路徑就是指連接兩點(diǎn)的這些路徑中最短的一條。我們有四種算法可以有效地解決最短路徑問(wèn)題。有一點(diǎn)需要讀者特別注意：邊的權(quán)值可以為負(fù)。當(dāng)出現(xiàn)負(fù)邊權(quán)時(shí)，有些算法不適用。一、求出最短路徑的長(zhǎng)度以下沒(méi)有特別說(shuō)明的話，disuv表示從u到v最短路徑長(zhǎng)度，wuv表示連接u，v的邊的長(zhǎng)度。1.Floyed-Warshall算法 O(N3) 簡(jiǎn)稱Floyed(弗洛伊德)算法，是最簡(jiǎn)單的最短路徑算法，可以計(jì)算圖中任意兩點(diǎn)間的最短路徑。Floyed的時(shí)間復(fù)雜度是O (N3)

2、，適用于出現(xiàn)負(fù)邊權(quán)的情況。算法描述： 初始化：點(diǎn)u、v如果有邊相連，則disuv=wuv。如果不相連則disuv=0 x7fffffffFor (k = 1; k = n; k+) For (i = 1; i = n; i+) For (j = 1; j disik + diskj) disij = disik + diskj; 算法結(jié)束：disij得出的就是從i到j(luò)的最短路徑。算法分析&思想講解：三層循環(huán)，第一層循環(huán)中間點(diǎn)k，第二第三層循環(huán)起點(diǎn)終點(diǎn)i、j，算法的思想很容易理解：如果點(diǎn)i到點(diǎn)k的距離加上點(diǎn)k到點(diǎn)j的距離小于原先點(diǎn)i到點(diǎn)j的距離，那么就用這個(gè)更短的路徑長(zhǎng)度來(lái)更新原先點(diǎn)i到

3、點(diǎn)j的距離。在上圖中，因?yàn)閐is13+dis32dis12，所以就用dis13+dis32來(lái)更新原先1到2的距離。我們?cè)诔跏蓟瘯r(shí)，把不相連的點(diǎn)之間的距離設(shè)為一個(gè)很大的數(shù)，不妨可以看作這兩點(diǎn)相隔很遠(yuǎn)很遠(yuǎn)，如果兩者之間有最短路徑的話，就會(huì)更新成最短路徑的長(zhǎng)度。Floyed算法的時(shí)間復(fù)雜度是O(N3)。 1 2 3 216 Floyed算法變形： 如果是一個(gè)沒(méi)有邊權(quán)的圖，把相連的兩點(diǎn)間的距離設(shè)為disij=true，不相連的兩點(diǎn)設(shè)為disij=false，用Floyed算法的變形：For (k = 1; k = n; k+) For (i = 1; i = n; i+) For (j = 1; j

4、= n; j+) disij = disij | (disik & diskj); 用這個(gè)辦法可以判斷一張圖中的兩點(diǎn)是否相連。 最后再?gòu)?qiáng)調(diào)一點(diǎn)：用來(lái)循環(huán)中間點(diǎn)的變量k必須放在最外面一層循環(huán)。【例4-1】、最短路徑問(wèn)題【問(wèn)題描述】平面上有n個(gè)點(diǎn)（n=100），每個(gè)點(diǎn)的坐標(biāo)均在-1000010000之間。其中的一些點(diǎn)之間有連線。若有連線，則表示可從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)，即兩點(diǎn)間有通路，通路的距離為兩點(diǎn)間的直線距離。現(xiàn)在的任務(wù)是找出從一點(diǎn)到另一點(diǎn)之間的最短路徑。【輸入格式】 輸入文件為short.in，共n+m+3行，其中: 第一行為整數(shù)n。 第2行到第n+1行（共n行） ，每行兩個(gè)整數(shù)x和y

5、，描述了一個(gè)點(diǎn)的坐標(biāo)。 第n+2行為一個(gè)整數(shù)m，表示圖中連線的個(gè)數(shù)。 此后的m 行，每行描述一條連線，由兩個(gè)整數(shù)i和j組成，表示第i個(gè)點(diǎn)和第j個(gè)點(diǎn)之間有連線。 最后一行：兩個(gè)整數(shù)s和t，分別表示源點(diǎn)和目標(biāo)點(diǎn)。 【輸出格式】 輸出文件為short.out，僅一行，一個(gè)實(shí)數(shù)（保留兩位小數(shù)），表示從s到t的最短路徑長(zhǎng)度。【輸入樣例輸入樣例】5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 【輸出樣例輸出樣例】3.41 【參考程序】#include#include#include#includeusing namespace std;int a1013;d

6、ouble f101101;int n,i,j,k,x,y,m,s,e;int main() freopen(short.in,r,stdin); freopen(short.out,w,stdout); cin n; for (i = 1; i ai1 ai2; cin m; memset(f,0 x7f,sizeof(f); /初始化f數(shù)組為最大值 for (i = 1; i x y; fyx = fxy = sqrt(pow(double(ax1-ay1),2)+pow(double(ax2-ay2),2); /pow(x,y)表示xy，其中x,y必須為double類型，要用cmath庫(kù)

7、 cin s e; for (k = 1; k = n; k+) /floyed 最短路算法 for (i = 1; i = n; i+) for (j = 1; j = n; j+) if (i != j) & (i != k) & (j != k) & (fik+fkj fij) fij = fik + fkj; printf(%.2lfn,fse); return 0;【例例4-2】牛的旅行牛的旅行【問(wèn)題描述問(wèn)題描述】農(nóng)民農(nóng)民JohnJohn的農(nóng)場(chǎng)里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一的農(nóng)場(chǎng)里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個(gè)

8、牧場(chǎng)。但是就目前而言，你能看到至少有兩片所有連通的牧區(qū)稱為一個(gè)牧場(chǎng)。但是就目前而言，你能看到至少有兩個(gè)牧區(qū)不連通。現(xiàn)在，個(gè)牧區(qū)不連通。現(xiàn)在，JohnJohn想在農(nóng)場(chǎng)里添加一條路徑想在農(nóng)場(chǎng)里添加一條路徑 ( ( 注意，恰好一注意，恰好一條條 ) )。對(duì)這條路徑有這樣的限制：一個(gè)牧場(chǎng)的直徑就是牧場(chǎng)中最遠(yuǎn)的兩。對(duì)這條路徑有這樣的限制：一個(gè)牧場(chǎng)的直徑就是牧場(chǎng)中最遠(yuǎn)的兩個(gè)牧區(qū)的距離個(gè)牧區(qū)的距離 ( ( 本題中所提到的所有距離指的都是最短的距離本題中所提到的所有距離指的都是最短的距離 ) )。考。考慮如下的兩個(gè)牧場(chǎng)，圖是有慮如下的兩個(gè)牧場(chǎng)，圖是有5 5個(gè)牧區(qū)的牧場(chǎng)，牧區(qū)用個(gè)牧區(qū)的牧場(chǎng)，牧區(qū)用“* *”表示

9、，路徑表示，路徑用直線表示。每一個(gè)牧區(qū)都有自己的坐標(biāo)：用直線表示。每一個(gè)牧區(qū)都有自己的坐標(biāo)： 圖所示的牧場(chǎng)的直徑大約是圖所示的牧場(chǎng)的直徑大約是12.07106, 12.07106, 最遠(yuǎn)的兩個(gè)牧區(qū)是最遠(yuǎn)的兩個(gè)牧區(qū)是A A和和E E，它們之間的最短路徑是，它們之間的最短路徑是A-B-EA-B-E。 這兩個(gè)牧場(chǎng)都在這兩個(gè)牧場(chǎng)都在JohnJohn的的農(nóng)場(chǎng)上。農(nóng)場(chǎng)上。JohnJohn將會(huì)在兩個(gè)牧場(chǎng)中各選一個(gè)牧區(qū)，然后用一條路徑連將會(huì)在兩個(gè)牧場(chǎng)中各選一個(gè)牧區(qū)，然后用一條路徑連起來(lái)，使得連通后這個(gè)新的更大的牧場(chǎng)有最小的直徑。注意，如果起來(lái)，使得連通后這個(gè)新的更大的牧場(chǎng)有最小的直徑。注意，如果兩條路徑中途相

10、交，我們不認(rèn)為它們是連通的。只有兩條路徑在同兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同一個(gè)牧區(qū)相交，我們才認(rèn)為它們是連通的。一個(gè)牧區(qū)相交，我們才認(rèn)為它們是連通的。 現(xiàn)在請(qǐng)你編程找現(xiàn)在請(qǐng)你編程找出一條連接兩個(gè)不同牧場(chǎng)的路徑，使得連上這條路徑后，這個(gè)更大出一條連接兩個(gè)不同牧場(chǎng)的路徑，使得連上這條路徑后，這個(gè)更大的新牧場(chǎng)有最小的直徑。的新牧場(chǎng)有最小的直徑。【輸入格式輸入格式】 第第 1 1 行：一個(gè)整數(shù)行：一個(gè)整數(shù)N (1 = N = N (1 = N = 150), 150), 表示牧區(qū)數(shù)；表示牧區(qū)數(shù)； 第第 2 2 到到 N+1 N+1 行：每行兩個(gè)整數(shù)行：每行兩個(gè)整數(shù)X X，Y

11、 ( 0 = XY ( 0 = X，Y= Y= 100000 )100000 )， 表示表示N N個(gè)牧區(qū)的坐標(biāo)。每個(gè)牧個(gè)牧區(qū)的坐標(biāo)。每個(gè)牧區(qū)的坐標(biāo)都是不一樣的。區(qū)的坐標(biāo)都是不一樣的。 第第 N+2 N+2 行行到第到第 2 2* *N+1 N+1 行：每行包括行：每行包括N N個(gè)數(shù)字個(gè)數(shù)字 ( 0( 0或或1 ) 1 ) 表示一個(gè)對(duì)稱鄰接矩陣。表示一個(gè)對(duì)稱鄰接矩陣。 例如，例如，題目描述中的兩個(gè)牧場(chǎng)的矩陣描述如下：題目描述中的兩個(gè)牧場(chǎng)的矩陣描述如下： A B C D E F G H A B C D E F G H A 0 1 0 0 0 0 0 0 A 0 1 0 0 0 0 0 0 B 1

12、0 1 1 1 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 H 0 0 0 0 0 0 1 0 輸入數(shù)據(jù)中至少包括兩個(gè)不連通的牧區(qū)。輸入數(shù)據(jù)中至少包括兩個(gè)不連通的牧區(qū)。【輸出格式輸出格式】 只有一行，

13、包括一個(gè)實(shí)數(shù)，表示所只有一行，包括一個(gè)實(shí)數(shù)，表示所求答案。數(shù)字保留六位小數(shù)。求答案。數(shù)字保留六位小數(shù)。【輸入樣例輸入樣例】 8 8 10 1010 10 15 1015 10 20 1020 10 15 1515 15 20 1520 15 30 1530 15 25 1025 10 30 1030 10 0100000001000000 1011100010111000 0100100001001000 0100100001001000 0111000001110000 0000001000000010 0000010100000101 0000001000000010【輸出樣例輸出樣例】

14、22.07106822.071068 【算法分析】 用Floyed求出任兩點(diǎn)間的最短路，然后求出每個(gè)點(diǎn)到所有可達(dá)的點(diǎn)的最大距離，記做mdisi。（Floyed算法） r1=max(mdisi) 然后枚舉不連通的兩點(diǎn)i,j，把他們連通，則新的直徑是mdisi+mdisj+(i,j)間的距離。 r2=min(mdisi+mdisj+disi,j) re=max(r1,r2) re就是所求。【參考程序參考程序】#include#include#include#includeusing namespace std;using namespace std;double f151151,m151,minx

15、,r,temp,x151,y151,maxint=1e12;double f151151,m151,minx,r,temp,x151,y151,maxint=1e12;double dist(int i,int j)double dist(int i,int j) return sqrt(xi-xj) return sqrt(xi-xj)* *(xi-xj)+(yi-yj)(xi-xj)+(yi-yj)* *(yi-yj) ; (yi-yj) ; int main()int main() int i,j,n,k;char c; int i,j,n,k;char c; cinn; cinn; f

16、or(i=1;ixiyi; for(i=1;ixiyi; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;jc; cinc; if(c=1)fij=dist(i,j); if(c=1)fij=dist(i,j); else fij=maxint; else fij=maxint; for(k=1;k=n;k+) for(k=1;k=n;k+) for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) if(i!=j&i!=k&j!=k) if(i

17、!=j&i!=k&j!=k) if(fikmaxint-1&fkjmaxint-1) if(fikmaxint-1&fkjfik+fkj) if(fijfik+fkj) fij=fik+fkj; fij=fik+fkj; memset(m,0,sizeof(m);memset(m,0,sizeof(m); for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) if(fijmaxint-1&mifij)mi=fij; if(fijmaxint-1&mifij)mi=fij;

18、minx=1e20; minx=1e20; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;jmaxint-1) if(i!=j&fijmaxint-1) temp=dist(i,j); temp=dist(i,j); if(minxmi+mj+temp)minx=mi+mj+temp; if(minxmi+mj+temp)minx=mi+mj+temp; r=0; r=0; for(i=1;iminx)minx=mi; for(i=1;iminx)minx=mi; printf(%.6lf,minx); printf(%

19、.6lf,minx); return 0; return 0; 2.2.Dijkstra算法算法O (N2)用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就是說(shuō)，只能計(jì)算起點(diǎn)只有一個(gè)的情況。是說(shuō)，只能計(jì)算起點(diǎn)只有一個(gè)的情況。Dijkstraijkstra的時(shí)間復(fù)雜度是的時(shí)間復(fù)雜度是O (N2)，它不能處理存在負(fù)邊權(quán)的情況。，它不能處理存在負(fù)邊權(quán)的情況。算法描述：算法描述： 設(shè)起點(diǎn)為設(shè)起點(diǎn)為s，disv表示從表示從s到到v的最短路徑，的最短路徑，prev為為v的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。的前驅(qū)節(jié)點(diǎn)，

20、用來(lái)輸出路徑。 a)a)初始化：初始化：disv=(vs); diss=0; pres=0 0; b)b)For (i = 1; i = n ; i+)(i = 1; i = n ; i+) 1.在沒(méi)有被訪問(wèn)過(guò)的點(diǎn)中找一個(gè)頂點(diǎn)在沒(méi)有被訪問(wèn)過(guò)的點(diǎn)中找一個(gè)頂點(diǎn)u使得使得disu是最小的。是最小的。 2.u標(biāo)記為已確定最短路徑標(biāo)記為已確定最短路徑 3.For 與與u相連的每個(gè)未確定最短路徑的頂點(diǎn)相連的每個(gè)未確定最短路徑的頂點(diǎn)v if ( (disu+wuv disv) ) disv = disu + wuv; prev = u; c)c)算法結(jié)束：算法結(jié)束：disv為為s到到v的最短距離；的最短距離

21、；prev為為v的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。算法分析算法分析&思想講解：思想講解： 從起點(diǎn)到一個(gè)點(diǎn)的最短路徑一定會(huì)經(jīng)過(guò)至少一個(gè)從起點(diǎn)到一個(gè)點(diǎn)的最短路徑一定會(huì)經(jīng)過(guò)至少一個(gè)“中轉(zhuǎn)點(diǎn)中轉(zhuǎn)點(diǎn)”（例如（例如下圖下圖1到到5的最短路徑，中轉(zhuǎn)點(diǎn)是的最短路徑，中轉(zhuǎn)點(diǎn)是2。特殊地，我們認(rèn)為起點(diǎn)。特殊地，我們認(rèn)為起點(diǎn)1也是一個(gè)也是一個(gè)“中中轉(zhuǎn)點(diǎn)轉(zhuǎn)點(diǎn)”）。顯而易見(jiàn)，如果我們想求出起點(diǎn)到一個(gè)點(diǎn)的最短路徑，那我們）。顯而易見(jiàn)，如果我們想求出起點(diǎn)到一個(gè)點(diǎn)的最短路徑，那我們必然要先求出中轉(zhuǎn)點(diǎn)的最短路徑（例如我們必須先求出點(diǎn)必然要先求出中轉(zhuǎn)點(diǎn)的最短路徑（例如我們必須先求出點(diǎn)2 的最短路徑后，的

22、最短路徑后，才能求出從起點(diǎn)到才能求出從起點(diǎn)到5的最短路徑）。的最短路徑）。中轉(zhuǎn)點(diǎn)中轉(zhuǎn)點(diǎn)終點(diǎn)終點(diǎn)最短路最短路1 11 10 01 1221、233 31、2、344 41、254 換句話說(shuō)，如果起點(diǎn)換句話說(shuō)，如果起點(diǎn)1到某一點(diǎn)到某一點(diǎn)V0的最短路徑要經(jīng)過(guò)中轉(zhuǎn)點(diǎn)的最短路徑要經(jīng)過(guò)中轉(zhuǎn)點(diǎn)Vi，那么，那么中轉(zhuǎn)點(diǎn)中轉(zhuǎn)點(diǎn)Vi一定是先于一定是先于V0被確定了最短路徑的點(diǎn)。被確定了最短路徑的點(diǎn)。 我們把點(diǎn)分為兩類，一類是已確定最短路徑的點(diǎn)，稱為我們把點(diǎn)分為兩類，一類是已確定最短路徑的點(diǎn)，稱為“白點(diǎn)白點(diǎn)”，另一類是未確定最，另一類是未確定最短路徑的點(diǎn)，稱為短路徑的點(diǎn)，稱為“藍(lán)點(diǎn)藍(lán)點(diǎn)”。如果我們要求出一個(gè)點(diǎn)的最短路

23、徑，就是把這個(gè)點(diǎn)由藍(lán)點(diǎn)變?yōu)椤Ｈ绻覀円蟪鲆粋€(gè)點(diǎn)的最短路徑，就是把這個(gè)點(diǎn)由藍(lán)點(diǎn)變?yōu)榘c(diǎn)。從起點(diǎn)到藍(lán)點(diǎn)的最短路徑上的中轉(zhuǎn)點(diǎn)在這個(gè)時(shí)刻只能是白點(diǎn)。白點(diǎn)。從起點(diǎn)到藍(lán)點(diǎn)的最短路徑上的中轉(zhuǎn)點(diǎn)在這個(gè)時(shí)刻只能是白點(diǎn)。 Dijkstra Dijkstra的算法思想，就是一開始將起點(diǎn)到起點(diǎn)的距離標(biāo)記為的算法思想，就是一開始將起點(diǎn)到起點(diǎn)的距離標(biāo)記為0，而后進(jìn)行，而后進(jìn)行n次循環(huán)，次循環(huán)，每次找出一個(gè)到起點(diǎn)距離每次找出一個(gè)到起點(diǎn)距離disu最短的點(diǎn)最短的點(diǎn)u，將它從藍(lán)點(diǎn)變?yōu)榘c(diǎn)。隨后枚舉所有的藍(lán)點(diǎn)，將它從藍(lán)點(diǎn)變?yōu)榘c(diǎn)。隨后枚舉所有的藍(lán)點(diǎn)vi，如果以此白點(diǎn)為中轉(zhuǎn)到達(dá)藍(lán)點(diǎn)如果以此白點(diǎn)為中轉(zhuǎn)到達(dá)藍(lán)點(diǎn)vi的路徑的路徑dis

24、u+wuvi更短的話，這將它作為更短的話，這將它作為vi的的“更短路更短路徑徑”disvi（此時(shí)還不確定是不是（此時(shí)還不確定是不是vi的最短路徑）。的最短路徑）。 就這樣，我們每找到一個(gè)白點(diǎn)，就嘗試著用它修改其他所有的藍(lán)點(diǎn)。中轉(zhuǎn)點(diǎn)先于終點(diǎn)就這樣，我們每找到一個(gè)白點(diǎn)，就嘗試著用它修改其他所有的藍(lán)點(diǎn)。中轉(zhuǎn)點(diǎn)先于終點(diǎn)變成白點(diǎn)，故每一個(gè)終點(diǎn)一定能夠被它的最后一個(gè)中轉(zhuǎn)點(diǎn)所修改，而求得最短路徑。變成白點(diǎn)，故每一個(gè)終點(diǎn)一定能夠被它的最后一個(gè)中轉(zhuǎn)點(diǎn)所修改，而求得最短路徑。123452471162求解順序讓我們對(duì)以上這段枯燥的文字做一番模擬，加深理解。讓我們對(duì)以上這段枯燥的文字做一番模擬，加深理解。 算法開始時(shí)

25、，作為起點(diǎn)的算法開始時(shí)，作為起點(diǎn)的dis1 = 0，其他的點(diǎn)，其他的點(diǎn)disi = 0 x7fffffffffffff。123452471162第一輪循環(huán)找到dis1最小，將1變成白點(diǎn)。對(duì)所有的藍(lán)點(diǎn)做出修改，使得dis2=2,dis3=4,dis4=7。這時(shí)這時(shí)dis2 2，dis3 3，dis4 4被它的最后一個(gè)中轉(zhuǎn)點(diǎn)被它的最后一個(gè)中轉(zhuǎn)點(diǎn)1修改為了最短路徑。修改為了最短路徑。123452471162第二輪循環(huán)找到dis2最小，將2變成白點(diǎn)。對(duì)所有的藍(lán)點(diǎn)做出修改，使得dis3=3,dis5=4。這時(shí)這時(shí)dis3，dis5被它們的最后一個(gè)中轉(zhuǎn)點(diǎn)被它們的最后一個(gè)中轉(zhuǎn)點(diǎn)2修改為了最短路徑。修改為了最

26、短路徑。123452471162第三輪循環(huán)找到dis3最小，將3變成白點(diǎn)。對(duì)所有的藍(lán)點(diǎn)做出修改，使得dis4=4。發(fā)現(xiàn)以3為中轉(zhuǎn)不能修改5，說(shuō)明3不是5的最后一個(gè)中轉(zhuǎn)點(diǎn)。這時(shí)這時(shí)dis4也被它的最后一個(gè)中轉(zhuǎn)點(diǎn)也被它的最后一個(gè)中轉(zhuǎn)點(diǎn)3修改為了最短路徑。修改為了最短路徑。接下來(lái)的兩輪循環(huán)將接下來(lái)的兩輪循環(huán)將4、5也變成白點(diǎn)。也變成白點(diǎn)。N輪循環(huán)結(jié)束后，所有的點(diǎn)的最短路徑即能求出。輪循環(huán)結(jié)束后，所有的點(diǎn)的最短路徑即能求出。Dijkstraijkstra無(wú)法處理邊權(quán)為負(fù)的情況，例如右圖這個(gè)例子。無(wú)法處理邊權(quán)為負(fù)的情況，例如右圖這個(gè)例子。2 2到到3的邊權(quán)值為的邊權(quán)值為-4，顯然從起點(diǎn)，顯然從起點(diǎn)1到到

27、3的最短路徑是的最短路徑是-2（123），但是），但是dijskstra在第二輪循環(huán)在第二輪循環(huán)開始時(shí)會(huì)找到當(dāng)前開始時(shí)會(huì)找到當(dāng)前disi最小的點(diǎn)最小的點(diǎn)3，并標(biāo)記它為白點(diǎn)。，并標(biāo)記它為白點(diǎn)。這時(shí)的這時(shí)的dis3=1，然而，然而1卻不是從起點(diǎn)到點(diǎn)卻不是從起點(diǎn)到點(diǎn)3的最短路徑。因?yàn)榈淖疃搪窂健Ｒ驗(yàn)?已被標(biāo)記為白點(diǎn)，最短路徑值已被標(biāo)記為白點(diǎn)，最短路徑值dis3不會(huì)再被修改了，所以我們?cè)谶厵?quán)存在負(fù)數(shù)的情況下得到了錯(cuò)誤的答案！不會(huì)再被修改了，所以我們?cè)谶厵?quán)存在負(fù)數(shù)的情況下得到了錯(cuò)誤的答案！12345213-4562【例例4-3】、最短路徑問(wèn)題、最短路徑問(wèn)題(Dijkstra) 題目參見(jiàn)題目參見(jiàn)“Floy

28、ed算法算法”，但本題要求使用，但本題要求使用dijkstra算法解決。算法解決。#include#include#include#includeusing namespace std;int a1013;double c101;bool b101;double f101101;int n,i,j,k,x,y,m,s,e;double minl;double maxx = 1e30;int main() cin n; for (i = 1; i ai1 ai2; for (i = 1; i = n; i+) for(j = 1; j m; for (i = 1; i x y; fxy = fy

29、x = = sqrt(pow(double(ax1-ay1),2)+pow(double(ax2-ay2),2); ; cin s e; for (i = 1; i = n; i+) ci = fsi; memset(b,false,sizeof(b); /dijkstra /dijkstra 最短路最短路 bs = true; cs = 0; for (i = 1; i = n-1; i+) minl = maxx; k = 0; for (j = 1; j = n; j+) / /查找可以更新的點(diǎn)查找可以更新的點(diǎn) if (! bj) & (cj minl) minl = cj; k

30、 = j; if (k = 0) break; bk = true; for (j = 1; j = n; j+) if (ck + fkj cj) cj = ck + fkj; printf(%.2lfn,ce); return 0;【例例4-4】最小花費(fèi)最小花費(fèi)【問(wèn)題描述問(wèn)題描述】 在在n n個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問(wèn)給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問(wèn)A A最少需要多少錢使得最少需

31、要多少錢使得轉(zhuǎn)賬后轉(zhuǎn)賬后B B收到收到100100元。元。【輸入格式輸入格式】 第一行輸入兩個(gè)正整數(shù)第一行輸入兩個(gè)正整數(shù)n,mn,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。 以下以下m m行每行輸入三個(gè)正整數(shù)行每行輸入三個(gè)正整數(shù)x,y,zx,y,z，表示標(biāo)號(hào)為，表示標(biāo)號(hào)為x x的人和標(biāo)號(hào)為的人和標(biāo)號(hào)為y y的人之間互相轉(zhuǎn)賬需要扣的人之間互相轉(zhuǎn)賬需要扣除除z%z%的手續(xù)費(fèi)的手續(xù)費(fèi) (z100)(z100)。 最后一行輸入兩個(gè)正整數(shù)最后一行輸入兩個(gè)正整數(shù)A,BA,B。數(shù)據(jù)保證。數(shù)據(jù)保證A A與與B B之間可以直接或間接地轉(zhuǎn)賬。之間可以直接或間接地轉(zhuǎn)賬。【

32、輸出格式輸出格式】 輸出輸出A A使得使得B B到賬到賬100100元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后8 8位。位。【輸入樣例輸入樣例】 3 3 3 3 1 2 1 1 2 1 2 3 2 2 3 2 1 3 3 1 3 3 1 3 1 3【輸出樣例輸出樣例】 103.07153164 103.07153164【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模】 1=n=2000 1=n=2000【參考程序參考程序】#include#includeusing namespace std;using namespace std;double a20012001,dis2001=0,minn;d

33、ouble a20012001,dis2001=0,minn;int n,m,i,j,k,x,y,f2001=0;int n,m,i,j,k,x,y,f2001=0;void init()void init() cinnm; cinnm; for(i=1;i=m;i+) for(i=1;ixy; cinxy; void dijkstra(int x)void dijkstra(int x) for(i=1;i=n;i+)disi=axi; for(i=1;i=n;i+)disi=axi; disx=1;fx=1; disx=1;fx=1; for(i=1;i=n-1;i+) for(i=1;i

34、=n-1;i+) minn=0; minn=0; for(j=1;j=n;j+) for(j=1;jminn)k=j;minn=disj; if(fj=0&disjminn)k=j;minn=disj; fk=1; fk=1; if(k=y)break; if(k=y)break; for(j=1;j=n;j+) for(j=1;jdisj)disj=diskakjdisj)disj=disk* *akj;akj; int main()int main() init(); init(); dijkstra(x); dijkstra(x); printf(%0.8lf,100/disy)

35、; printf(%0.8lf,100/disy); return 0; return 0; 3.3.Bellman-Ford算法算法O(NE)簡(jiǎn)稱簡(jiǎn)稱FordFord（福特）算法，同樣是用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算（福特）算法，同樣是用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，也是一種單源最短路徑算法。法，也是一種單源最短路徑算法。能夠處理存在負(fù)邊權(quán)的情況，但無(wú)法處理存在負(fù)權(quán)回路的情況（下文會(huì)有詳細(xì)說(shuō)能夠處理存在負(fù)邊權(quán)的情況，但無(wú)法處理存在負(fù)權(quán)回路的情況（下文會(huì)有詳細(xì)說(shuō)明）。明）。算法時(shí)間復(fù)雜度：算法時(shí)間復(fù)雜度：O(NE)，N是頂點(diǎn)數(shù)，是頂點(diǎn)數(shù)，E是邊數(shù)。是邊數(shù)。算法實(shí)現(xiàn)：算

36、法實(shí)現(xiàn)：設(shè)設(shè)s為起點(diǎn)，為起點(diǎn)，disv即為即為s到到v的最短距離，的最短距離，prev為為v前驅(qū)。前驅(qū)。wj是邊是邊j的長(zhǎng)度，且的長(zhǎng)度，且j連連接接u、v。初始化：初始化：diss=0,disv=（vs），），pres=0For (i = 1; i = n-1; i+)(i = 1; i = n-1; i+)For (j = 1; j = E; j+)(j = 1; j = E; j+) / /注意要枚舉所有邊，不能枚舉點(diǎn)。注意要枚舉所有邊，不能枚舉點(diǎn)。 if ( (disu+wjdisv) ) /u /u、v分別是這條邊連接的兩個(gè)點(diǎn)。分別是這條邊連接的兩個(gè)點(diǎn)。 disv =disu + wj

37、; prev = u; 算法分析算法分析& &思想講解：思想講解：Bellman-Ford算法的思想很簡(jiǎn)單。一開始認(rèn)為起點(diǎn)是白點(diǎn)算法的思想很簡(jiǎn)單。一開始認(rèn)為起點(diǎn)是白點(diǎn)(dis1=0)，每一次都枚舉所有的邊，必然，每一次都枚舉所有的邊，必然會(huì)有一些邊，連接著白點(diǎn)和藍(lán)點(diǎn)。因此每次都能用所有的白點(diǎn)去修改所有的藍(lán)點(diǎn)，每次循環(huán)也必然會(huì)有一些邊，連接著白點(diǎn)和藍(lán)點(diǎn)。因此每次都能用所有的白點(diǎn)去修改所有的藍(lán)點(diǎn)，每次循環(huán)也必然會(huì)有至少一個(gè)藍(lán)點(diǎn)變成白點(diǎn)。會(huì)有至少一個(gè)藍(lán)點(diǎn)變成白點(diǎn)。在上面這個(gè)簡(jiǎn)單的模擬中能看到白點(diǎn)的在上面這個(gè)簡(jiǎn)單的模擬中能看到白點(diǎn)的“蔓延蔓延”情況。情況。負(fù)權(quán)回路：負(fù)權(quán)回路：雖然雖然B

38、ellman-Ford算法可以求出存在負(fù)邊權(quán)情況下的最短路徑，卻無(wú)法解決存在負(fù)權(quán)回算法可以求出存在負(fù)邊權(quán)情況下的最短路徑，卻無(wú)法解決存在負(fù)權(quán)回路的情況。路的情況。 負(fù)權(quán)回路是指邊權(quán)之和為負(fù)數(shù)的一條回路，上圖中負(fù)權(quán)回路是指邊權(quán)之和為負(fù)數(shù)的一條回路，上圖中- - - - -這條回路的邊權(quán)之和為這條回路的邊權(quán)之和為-3。在有負(fù)權(quán)回路的情況下，從在有負(fù)權(quán)回路的情況下，從1到到6的最短路徑是多少？答案是無(wú)窮小，因?yàn)槲覀兛梢岳@這條負(fù)權(quán)回的最短路徑是多少？答案是無(wú)窮小，因?yàn)槲覀兛梢岳@這條負(fù)權(quán)回路走無(wú)數(shù)圈，每走一圈路徑值就減去路走無(wú)數(shù)圈，每走一圈路徑值就減去3，最終達(dá)到無(wú)窮小。，最終達(dá)到無(wú)窮小。所以說(shuō)存在負(fù)權(quán)

39、回路的圖無(wú)法求出最短路徑，所以說(shuō)存在負(fù)權(quán)回路的圖無(wú)法求出最短路徑，Bellman-Ford算法可以在有負(fù)權(quán)回路的情況下算法可以在有負(fù)權(quán)回路的情況下輸出錯(cuò)誤提示。輸出錯(cuò)誤提示。 如果在如果在Bellman-Ford算法的兩重循環(huán)完成后，還是存在某條邊使得：算法的兩重循環(huán)完成后，還是存在某條邊使得：disu+wdisv，則存在負(fù)權(quán)回路：則存在負(fù)權(quán)回路：ForFor每條邊每條邊(u,v) (u,v) I If f ( (disu+wdisvdisu+wdisv) ) return False return False如果我們規(guī)定每條邊只能走一次，在這個(gè)前提下可以求出負(fù)權(quán)回路的最短路徑。這個(gè)問(wèn)題就如果

40、我們規(guī)定每條邊只能走一次，在這個(gè)前提下可以求出負(fù)權(quán)回路的最短路徑。這個(gè)問(wèn)題就留待讀者自己思考（提示：對(duì)留待讀者自己思考（提示：對(duì)Floyed做一點(diǎn)小處理）。做一點(diǎn)小處理）。【例【例4-5】、最短路徑問(wèn)題、最短路徑問(wèn)題(Bellman-Ford) 題目參見(jiàn)題目參見(jiàn)“Floyed算法算法”，要求采用，要求采用Bellman-Ford算法。算法。#include#include#includeusing namespace std;int main() double a1013,dis1001,w1001,min1; int n,m,x,y,k,f10013,s,t; bool b101; cinn

41、; for (int i=1;im; for (int i=1;i=m;i+) /初始化數(shù)組初始化數(shù)組dis，f disi=0 x7fffffffffffff/3/3; fi1 = fi2 = fi1 = fi2 = 0 x7fffffffffffff/3/3; for (int i=1;ist; diss=0; for (int i=1;i=n;i+) / /算法主體算法主體 for (int j=1;j=m;j+) if (disfj1+wjdisfj2) disfj2=disfj1+wj; if (disfj2+wjdisu+wudisvdisu+wuvv) ) disv=disu+wu

42、 disv=disu+wuv;v; prev=u; prev=u; i if f (!(!existvexistv) ) / /隊(duì)列中不存在隊(duì)列中不存在v v點(diǎn)，點(diǎn)，v v入隊(duì)。入隊(duì)。 / /尾指針下移一位，尾指針下移一位，v v入隊(duì)入隊(duì); ; e existv=true;xistv=true; while (head tail); while (head tail);循環(huán)隊(duì)列：采用循環(huán)隊(duì)列能夠降低隊(duì)列大小，隊(duì)列長(zhǎng)度只需開到2*n+5即可。例題中的參考程序使用了循環(huán)隊(duì)列。【例例4-6】、香甜的黃油、香甜的黃油(Sweet Butter) )【問(wèn)題描述問(wèn)題描述】農(nóng)夫農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛

43、州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道N（1=N=500）只奶牛會(huì)過(guò)來(lái)舔它，這樣就能做出能賣好價(jià)錢的超）只奶牛會(huì)過(guò)來(lái)舔它，這樣就能做出能賣好價(jià)錢的超甜黃油。當(dāng)然，他將付出額外的費(fèi)用在奶牛上。甜黃油。當(dāng)然，他將付出額外的費(fèi)用在奶牛上。 農(nóng)夫農(nóng)夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們?cè)诼牭解徛晻r(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里然后下午發(fā)出鈴聲，以至很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們?cè)诼牭解徛晻r(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠

44、奶。他可以在晚上擠奶。農(nóng)夫農(nóng)夫John知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng)知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng)（他將把糖放在那）。（他將把糖放在那）。 【輸入格式輸入格式】butter.in第一行第一行: 三個(gè)數(shù)：奶牛數(shù)三個(gè)數(shù)：奶牛數(shù)N，牧場(chǎng)數(shù)，牧場(chǎng)數(shù)P（2=P=800），牧場(chǎng)間道路數(shù)），牧場(chǎng)間道路數(shù)C(1=C=1450)。第二行到第第二行到第N+1行行: 1到到N頭奶牛所在的牧場(chǎng)號(hào)。頭奶牛所在的牧場(chǎng)號(hào)。第第N+

45、2行到第行到第N+C+1行：每行有三個(gè)數(shù)：相連的牧場(chǎng)行：每行有三個(gè)數(shù)：相連的牧場(chǎng)A、B，兩牧場(chǎng)間距（，兩牧場(chǎng)間距（1=D=255），當(dāng)然，連接是雙向的。），當(dāng)然，連接是雙向的。【輸出格式輸出格式】butter.out 一行一行 輸出奶牛必須行走的最小的距離和輸出奶牛必須行走的最小的距離和.【輸入樣例輸入樣例】3 4 52341 2 11 3 52 3 72 4 33 4 5樣例圖形樣例圖形 P2 P2 P1 -1- C1P1 -1- C1 | | | | 5 7 3 5 7 3 | | | C3 | C3 C2 -5- C2 -5- P3 P4 P3 P4【輸出樣例輸出樣例】8 / /說(shuō)明：放

46、在說(shuō)明：放在4號(hào)牧場(chǎng)最優(yōu)號(hào)牧場(chǎng)最優(yōu)【參考程序參考程序】#include#include#include#include#include#includeusing namespace std;using namespace std;int n,p,c,i,j,x,y,t,min1,head,tail,tot,u;int n,p,c,i,j,x,y,t,min1,head,tail,tot,u;int a801801,b501,dis801,num801,w801801,team1601;int a801801,b501,dis801,num801,w801801,team1601;bool ex

47、ist801;bool exist801;int main()int main() freopen(butter.in,r,stdin); freopen(butter.in,r,stdin); freopen(butter.out,w,stdout); freopen(butter.out,w,stdout); cinnpc; cinnpc; for(i=1;i=p;i+) for(i=1;i=p;i+) bi=0;bi=0; numi=0;numi=0; for(j=1;j=p;j+) for(j=1;j=p;j+) wij= wij=0 x7fffffff/30 x7fffffff/3;

48、 ; for(i=1;i=n;i+) for(i=1;ibi; cinbi; for(i=1;i=c;i+) for(i=1;ixyt; cinxyt; wxy=t; wxy=t; ax+numx=y; ax+numx=y; ay+numy=x; ay+numy=x; wyx=wxy; wyx=wxy; min1= min1=0 x7fffffff0 x7fffffff/3/3; ; for(i=1;i=p;i+) for(i=1;i=p;i+) for(j=1;j=p;j+) disj= for(j=1;j=p;j+) disj=0 x7fffffff0 x7fffffff/3/3; ; m

49、emset(team,0,sizeof(team); memset(team,0,sizeof(team); / /隊(duì)列數(shù)組初始化隊(duì)列數(shù)組初始化 memset(exist,false,sizeof(exist); memset(exist,false,sizeof(exist); /exist /exist標(biāo)志初始化標(biāo)志初始化 disi=0;team1=i;head=0;tail=1;existi=true; disi=0;team1=i;head=0;tail=1;existi=true; / /起始點(diǎn)入隊(duì)起始點(diǎn)入隊(duì) do do head+; head+; head=(head-1)%160

50、1)+1; head=(head-1)%1601)+1; / /循環(huán)隊(duì)列處理循環(huán)隊(duì)列處理 u=teamhead; u=teamhead; existu=false; existu=false; for(j=1;j= for(j=1;jdisu+wuauj) if (disaujdisu+wuauj) disauj=disu+wuauj; disauj=disu+wuauj; if (!existauj) if (!existauj) tail+; tail+; tail=(tail-1)%1601)+1; tail=(tail-1)%1601)+1; teamtail=auj; teamtai

51、l=auj; existauj=true; existauj=true; while(head!=tail); while(head!=tail); tot=0; tot=0; for(j=1;j=n;j+) for(j=1;j=n;j+) t totot+ +=disbj;=disbj; if (totmin1) min1=tot; if (totmin1) min1=tot; coutmin1; coutmin1; return 0; return 0; 二、輸出最短路徑二、輸出最短路徑1.1.單源最短路徑的輸出單源最短路徑的輸出Dijkstraijkstra，Bellman-Ford，S

52、PFA都是單源最短路徑算法，它們的共同點(diǎn)是都都是單源最短路徑算法，它們的共同點(diǎn)是都有一個(gè)數(shù)組有一個(gè)數(shù)組prex 用來(lái)記錄從起點(diǎn)到用來(lái)記錄從起點(diǎn)到x的最短路徑中，的最短路徑中，x的前驅(qū)結(jié)點(diǎn)是哪個(gè)。的前驅(qū)結(jié)點(diǎn)是哪個(gè)。每次更新，我們就給每次更新，我們就給prex 賦一個(gè)新值，結(jié)合上面的思想講解，相信對(duì)于記錄賦一個(gè)新值，結(jié)合上面的思想講解，相信對(duì)于記錄某點(diǎn)的前驅(qū)結(jié)點(diǎn)是不難理解的。那么怎么利用某點(diǎn)的前驅(qū)結(jié)點(diǎn)是不難理解的。那么怎么利用prex 數(shù)組輸出最短路徑方案呢？數(shù)組輸出最短路徑方案呢？【例【例4-7】、最短路徑問(wèn)題】、最短路徑問(wèn)題(輸出路徑輸出路徑)要求改寫程序，用要求改寫程序，用Dijkstra、

53、Bellman-Ford、SPFA算法輸出最短路徑的方案。算法輸出最短路徑的方案。使用一個(gè)小小的遞歸過(guò)程就能解決這一問(wèn)題。使用一個(gè)小小的遞歸過(guò)程就能解決這一問(wèn)題。void print(int x) if (pre if (preax = 0) return; /x = 0) return; /起點(diǎn)的前驅(qū)我們已設(shè)為起點(diǎn)的前驅(qū)我們已設(shè)為0print(preax); cout x; / /主程序中：主程序中：mainmain （進(jìn)行（進(jìn)行Dijkstra或或Bellman-Ford，SPFA運(yùn)算）運(yùn)算）cout sout s; print print(e); /s /s是起點(diǎn)，是起點(diǎn)，e是終點(diǎn)是終點(diǎn)

54、 2.2.Floyed算法輸出最短路徑算法輸出最短路徑FloyedFloyed算法輸出路徑也是采用記錄前驅(qū)點(diǎn)的方式。因?yàn)樗惴ㄝ敵雎窂揭彩遣捎糜涗浨膀?qū)點(diǎn)的方式。因?yàn)閒loyed是計(jì)算任意兩點(diǎn)是計(jì)算任意兩點(diǎn)間最短路徑的算法，間最短路徑的算法，disij記錄從記錄從i到到j(luò)的最短路徑值。故而我們定義的最短路徑值。故而我們定義preij為一個(gè)二維數(shù)組，記錄從為一個(gè)二維數(shù)組，記錄從i到到j(luò)的最短路徑中，的最短路徑中，j的前驅(qū)點(diǎn)是哪一個(gè)。的前驅(qū)點(diǎn)是哪一個(gè)。【例例4-8】、最短路徑問(wèn)題、最短路徑問(wèn)題(Floyed法輸出路徑法輸出路徑)要求改寫要求改寫Floyed的程序，模仿的程序，模仿Dijkstra輸出路

55、徑的方法用輸出路徑的方法用floyed輸出最短路徑方案。輸出最短路徑方案。【參考程序參考程序】#include#include#includeusing namespace std;double dis101101;int x101,y101;int pre101101;int n,i,j,k,m,a,b;int pf(int x) return x*x;void print(int x) if (preax = 0) return; /prea if (preax = 0) return; /preaa=0,a=0,說(shuō)明已經(jīng)遞歸到起點(diǎn)說(shuō)明已經(jīng)遞歸到起點(diǎn)a print(preax); cout

56、 n; cin n; for (i = 1; i = n; i+) for (i = 1; i xi yi; cin xi yi; memset(dis,0 x7f,sizeof(dis); memset(dis,0 x7f,sizeof(dis); /初始化數(shù)組初始化數(shù)組 cin m; cin m; memset(pre,0,sizeof(pre); memset(pre,0,sizeof(pre); / /初始化前驅(qū)數(shù)組初始化前驅(qū)數(shù)組 for (i = 1; i = m; i+) for (i = 1; i a b; cin a b; disab = disba = sqrt(pf(xa-

57、xb)+pf(ya-yb); disab = disba = sqrt(pf(xa-xb)+pf(ya-yb); preab = a; preab = a; /a /a與與b b相連，自然從相連，自然從a a到到b b的最短路徑的最短路徑b b的前驅(qū)是的前驅(qū)是a a preba = b; preba = b; cin a b; cin a b; for (k = 1; k = n; k+) for (k = 1; k = n; k+) /floyed /floyed 最短路最短路 for (i = 1; i = n; i+) for (i = 1; i = n; i+) for (j = 1;

58、 j = n; j+) for (j = 1; j disik+diskj) if (disij disik+diskj) disij = disik + diskj; disij = disik + diskj; preij = prekj; preij = prekj; / /從從i i到到j(luò) j的最短路徑更新為的最短路徑更新為i ik kj j，那么，那么i i到到j(luò) j最短路徑最短路徑j(luò) j的前驅(qū)就肯定與的前驅(qū)就肯定與k k到到j(luò) j最短路徑最短路徑j(luò) j的前驅(qū)相同。的前驅(qū)相同。 cout a; cout a; print(b); /a print(b); /a是起點(diǎn)，是起點(diǎn)，b b是

59、終點(diǎn)是終點(diǎn) return 0; return 0; 最后再稍微提一提有向圖求最短路徑的方法：對(duì)有向圖求最短路徑上面的算法可以直接使用，只需注意如最后再稍微提一提有向圖求最短路徑的方法：對(duì)有向圖求最短路徑上面的算法可以直接使用，只需注意如果從果從i到到j(luò)只有一條有向邊，只有一條有向邊，wij賦值為這條邊的權(quán)值，而將賦值為這條邊的權(quán)值，而將wji賦值為無(wú)窮大即可。賦值為無(wú)窮大即可。【上機(jī)練習(xí)】1、信使【問(wèn)題描述】 戰(zhàn)爭(zhēng)時(shí)期，前線有n個(gè)哨所，每個(gè)哨所可能會(huì)與其他若干個(gè)哨所之間有通信聯(lián)系。信使負(fù)責(zé)在哨所之間傳遞信息，當(dāng)然，這是要花費(fèi)一定時(shí)間的（以天為單位）。指揮部設(shè)在第一個(gè)哨所。當(dāng)指揮部下達(dá)一個(gè)命令后

60、，指揮部就派出若干個(gè)信使向與指揮部相連的哨所送信。當(dāng)一個(gè)哨所接到信后，這個(gè)哨所內(nèi)的信使們也以同樣的方式向其他哨所送信。直至所有n個(gè)哨所全部接到命令后，送信才算成功。因?yàn)闇?zhǔn)備充足，每個(gè)哨所內(nèi)都安排了足夠的信使（如果一個(gè)哨所與其他k個(gè)哨所有通信聯(lián)系的話，這個(gè)哨所內(nèi)至少會(huì)配備k個(gè)信使）。 現(xiàn)在總指揮請(qǐng)你編一個(gè)程序，計(jì)算出完成整個(gè)送信過(guò)程最短需要多少時(shí)間。【輸入格式】 輸入文件msner.in，第1行有兩個(gè)整數(shù)n和m，中間用1個(gè)空格隔開，分別表示有n個(gè)哨所和m條通信線路。1=n=100。 第2至m+1行：每行三個(gè)整數(shù)i、j、k，中間用1個(gè)空格隔開，表示第i個(gè)和第j個(gè)哨所之間存在通信線路，且這條線路要花費(fèi)k天。【輸出格式】 輸出文件msner.out，僅一個(gè)整數(shù)，表示完成整個(gè)送信過(guò)程的最短時(shí)間。如果不是所有的哨所都能收到信，就輸出-1。 【輸入