第節(jié)圖論算法(C++)

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

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

4、+) disij = disij | (disik & diskj); 用這個(gè)辦法可以判斷一張圖中的兩點(diǎn)是否相連。 最后再強(qiáng)調(diào)一點(diǎn)：用來循環(huán)中間點(diǎn)的變量k必須放在最外面一層循環(huán)?！纠?-1】、最短路徑問題【問題描述】平面上有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)間的直線距離?，F(xiàn)在的任務(wù)是找出從一點(diǎn)到另一點(diǎn)之間的最短路徑?！据斎敫袷健?輸入文件為short.in，共n+m+3行，其中: 第一行為整數(shù)n。 第2行到第n+1行（共n行） ，每行兩個(gè)整數(shù)x和y，描述了一個(gè)

5、點(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)度?！据斎霕永斎霕永? 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;double

6、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庫 cin s

7、 e; for (k = 1; k = n; k+) /floyd 最短路算法 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】牛的旅行牛的旅行【問題描述問題描述】農(nóng)民農(nóng)民JohnJohn的農(nóng)場(chǎng)里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一的農(nóng)場(chǎng)里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個(gè)牧場(chǎng)。但是就目

8、前而言，你能看到至少有兩片所有連通的牧區(qū)稱為一個(gè)牧場(chǎng)。但是就目前而言，你能看到至少有兩個(gè)牧區(qū)不連通?，F(xiàn)在，個(gè)牧區(qū)不連通?，F(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ū)，然后用一條路徑連起來，使得連通后這個(gè)新的更大的牧場(chǎng)有最小的直徑。注意，如果起來，使得連通后這個(gè)新的更大的牧場(chǎng)有最小的直徑。注意，如果兩條路徑中途相交，我們不認(rèn)為

10、它們是連通的。只有兩條路徑在同兩條路徑中途相交，我們不認(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 ( 0 =

11、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 0 1 1 1

12、 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ū)?！据敵龈袷捷敵龈袷健?只有一行，包括一個(gè)實(shí)數(shù)，

13、表示所只有一行，包括一個(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【輸出樣例輸出樣例】 22.0710

14、6822.071068 【算法分析】 用Floyd求出任兩點(diǎn)間的最短路，然后求出每個(gè)點(diǎn)到所有可達(dá)的點(diǎn)的最大距離，記做mdisi。（Floyd算法） 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,r,temp,x

15、151,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; for(i=1;ix

16、iyi; 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!=j&i

17、!=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; minx=1e20

18、; 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(%.6lf,minx

19、); return 0; return 0; 2.2.Dijkstra算法算法O (N2)用來計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就用來計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就是說，只能計(jì)算起點(diǎn)只有一個(gè)的情況。是說，只能計(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)，用來輸出路徑。的前驅(qū)節(jié)點(diǎn)，用來輸出路徑。 a

20、)a)初始化：初始化：disv=(vs); diss=0; pres=0 0; b)b)For (i = 1; i = n ; i+)(i = 1; i = n ; i+) 1.在沒有被訪問過的點(diǎn)中找一個(gè)頂點(diǎn)在沒有被訪問過的點(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的最短距離；的最短距離；prev為為v的

21、前驅(qū)節(jié)點(diǎn)，用來輸出路徑。的前驅(qū)節(jié)點(diǎn)，用來輸出路徑。算法分析算法分析&思想講解：思想講解： 從起點(diǎn)到一個(gè)點(diǎn)的最短路徑一定會(huì)經(jīng)過至少一個(gè)從起點(diǎn)到一個(gè)點(diǎn)的最短路徑一定會(huì)經(jīng)過至少一個(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)”）。顯而易見，如果我們想求出起點(diǎn)到一個(gè)點(diǎ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 換句話說，如果起點(diǎn)換句話說，如果起點(diǎn)1到某一點(diǎn)到某一點(diǎn)V0的最短路徑要經(jīng)過中轉(zhuǎn)點(diǎn)的最短路徑要經(jīng)過中轉(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)的最短路徑，就是把這個(gè)點(diǎn)由

23、藍(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的路徑的路徑disu+wuvi更短的

24、話，這將它作為更短的話，這將它作為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í)，作為起點(diǎn)的算法開

25、始時(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修改為了最短路徑。修改為了最短路徑。12345

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

27、短路徑是-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】、最短路徑問題、最短路徑問題(Dijkstra) 題目參見題目參見“Floyd算法算法”，但本

28、題要求使用，但本題要求使用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 = fyx = = sqrt

29、(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 = j; if (

30、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)【問題描述問題描述】 在在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)問給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問A A最少需要多少錢使得最少需要多少錢使得轉(zhuǎn)賬后轉(zhuǎn)

31、賬后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;double a200

33、12001,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=n-1;i+) m

34、inn=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.8f,100/disy); printf(%0

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

36、起點(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; prev = u;

37、算法分析算法分析& &思想講解：思想講解：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)回路：雖然雖然Bellman-Ford算

38、法可以求出存在負(fù)邊權(quán)情況下的最短路徑，卻無法解決存在負(fù)權(quán)回算法可以求出存在負(fù)邊權(quán)情況下的最短路徑，卻無法解決存在負(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的最短路徑是多少？答案是無窮小，因?yàn)槲覀兛梢岳@這條負(fù)權(quán)回的最短路徑是多少？答案是無窮小，因?yàn)槲覀兛梢岳@這條負(fù)權(quán)回路走無數(shù)圈，每走一圈路徑值就減去路走無數(shù)圈，每走一圈路徑值就減去3，最終達(dá)到無窮小。，最終達(dá)到無窮小。所以說存在負(fù)權(quán)回路的圖無法求出最短路徑

39、，所以說存在負(fù)權(quán)回路的圖無法求出最短路徑，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è)問題就如果我們規(guī)定每條邊只能走一次

40、，在這個(gè)前提下可以求出負(fù)權(quán)回路的最短路徑。這個(gè)問題就留待讀者自己思考（提示：對(duì)留待讀者自己思考（提示：對(duì)Floyd做一點(diǎn)小處理）。做一點(diǎn)小處理）?！纠纠?-5】、最短路徑問題、最短路徑問題(Bellman-Ford) 題目參見題目參見“Floyd算法算法”，要求采用，要求采用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; for (int i=1

41、;im; for (int i=1;i=m;i+) /初始化數(shù)組初始化數(shù)組dis，f disi=0 x7fffffffffffff; fi1 = fi2 = fi1 = fi2 = 0 x7fffffffffffff; 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 disv=disu+wuv;v; prev

42、=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ì)列?！纠?-6】、香甜的黃油、香甜的黃油(Sweet Butter) )【問題描述問題描述】農(nóng)夫農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，

43、他知道發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道N（1=N=500）只奶牛會(huì)過來舔它，這樣就能做出能賣好價(jià)錢的超）只奶牛會(huì)過來舔它，這樣就能做出能賣好價(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ā)出鈴聲，以至他可以在晚上擠奶。他可以在晚上擠奶。農(nóng)夫農(nóng)夫John知道每

44、只奶牛都在各自喜歡的牧場(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+2行到第行到第N+C+1行：每行有三個(gè)數(shù)：相

45、連的牧場(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 / /說明：放在說明：放在4號(hào)牧場(chǎng)最優(yōu)號(hào)牧場(chǎng)最優(yōu)【參考程序

46、參考程序】#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,w801801,team1601;int a801801,b501,dis801,w801801,team1601;bool exist801;bool exist801;int main()int m

47、ain() 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; ai0=0;ai0=0; for(j=1;j=p;j+) for(j=1;j=p;j+) wij= wij=0 x7fffffff0 x7fffffff; ; for(i=1;i=n;i+) for(i=1;ibi; cinbi; for

48、(i=1;i=c;i+) for(i=1;ixyt; cinxyt; wxy=t; wxy=t; ax+ax0=y; ax+ax0=y; ay+ay0=x; ay+ay0=x; wyx=wxy; wyx=wxy; min1= min1=0 x7fffffff0 x7fffffff; ; for(i=1;i=p;i+) for(i=1;i=p;i+) for(j=1;j=p;j+) for(j=1;j=p;j+) disj= disj=0 x7fffffff0 x7fffffff; ; memset(team,0,sizeof(team); memset(team,0,sizeof(team);

49、 / /隊(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)%1601)+1; head=(head-1)%1601)+1; / /循環(huán)隊(duì)列處理循環(huán)隊(duì)列處理 u=teamhea

50、d; u=teamhead; existu=false; existu=false; for(j=1;j=au0;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; teamtail=auj; existauj=true; existauj=true; while(head

51、!=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，SPFA都是單源最短路徑算法，它們的共同點(diǎn)是都都是單源最短路徑算法，它們的共同點(diǎn)是都有一個(gè)數(shù)組有

52、一個(gè)數(shù)組prex 用來記錄從起點(diǎn)到用來記錄從起點(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】、最短路徑問題】、最短路徑問題(輸出路徑輸出路徑)要求改寫程序，用要求改寫程序，用Dijkstra、Bellman-Ford、SPFA算法輸出最短路徑的方案。算法輸出最短路徑的方案。使用一個(gè)小小

53、的遞歸過程就能解決這一問題。使用一個(gè)小小的遞歸過程就能解決這一問題。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) 2.2.Floyd算法輸出最短路徑算法輸出最短路徑FloydFloyd算法輸出路徑也是采用記

54、錄前驅(qū)點(diǎn)的方式。因?yàn)樗惴ㄝ敵雎窂揭彩遣捎糜涗浨膀?qū)點(diǎn)的方式。因?yàn)閒loyd是計(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è)?！纠?-8】、最短路徑問題、最短路徑問題(Floyd法法輸出路徑輸出路徑)要求要求改寫改寫Floyd的的程序，模仿程序，模仿Dijkstra輸出路徑的方法輸出路徑的方法用用floyd輸出輸出最短路徑方案。最短路徑方案?！緟⒖汲绦騾⒖汲绦颉?includ

55、e#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,說明已經(jīng)遞歸到起點(diǎn)說明已經(jīng)遞歸到起點(diǎn)a print(preax); cout n; cin n; for (i = 1; i = n; i+) for (i = 1; i xi yi;

56、 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-xb)+pf(ya-yb); disab = disba = sqrt(pf(xa-xb)+pf(ya-yb

57、); 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+) /floyd /floyd 最短路最短路 for (i = 1; i = n; i+) for (i = 1; i = n; i+) for (j = 1; j = n; j+) for (j = 1; j disik+diskj) if (disij disik+d

58、iskj) 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是終點(diǎn)是終點(diǎn) return 0; return 0; 最后再稍微提一提有向圖求最短路徑的方法：對(duì)有向圖求最短路徑上

59、面的算法可以直接使用，只需注意如最后再稍微提一提有向圖求最短路徑的方法：對(duì)有向圖求最短路徑上面的算法可以直接使用，只需注意如果從果從i到到j(luò)只有一條有向邊，只有一條有向邊，wij賦值為這條邊的權(quán)值，而將賦值為這條邊的權(quán)值，而將wji賦值為無窮大即可。賦值為無窮大即可?！旧蠙C(jī)練習(xí)】1、信使【問題描述】 戰(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è)命令后，指揮部就派出若干個(gè)信使向與指揮部相連的哨所送信。當(dāng)一個(gè)哨所接到信后，這個(gè)哨所內(nèi)的信使們也以同樣的方式向其他哨所

60、送信。直至所有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è)送信過程最短需要多少時(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è)送信過程的最短時(shí)間。如果不是所有的哨所都能收到信，就輸出-1。 【輸入樣例】 4 4 1 2 4 2 3 7 2 4 1 3 4 6 【輸出樣例】 112 2、最優(yōu)乘車、最優(yōu)乘車【問