信息學奧賽一本通 第4章第3-4節(jié) 圖論算法(C++版)

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

2、，適用于出現(xià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的最短路徑。算法分析&思想講解：三層循環(huán)，第一層循環(huán)中間點k，第二第三層循環(huán)起點終點i、j，算法的思想很容易理解：如果點i到點k的距離加上點k到點j的距離小于原先點i到點j的距離，那么就用這個更短的路徑長度來更新原先點i到

3、點j的距離。在上圖中，因為dis13+dis32dis12，所以就用dis13+dis32來更新原先1到2的距離。我們在初始化時，把不相連的點之間的距離設為一個很大的數(shù)，不妨可以看作這兩點相隔很遠很遠，如果兩者之間有最短路徑的話，就會更新成最短路徑的長度。Floyed算法的時間復雜度是O(N3)。 1 2 3 216 Floyed算法變形： 如果是一個沒有邊權的圖，把相連的兩點間的距離設為disij=true，不相連的兩點設為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); 用這個辦法可以判斷一張圖中的兩點是否相連。 最后再強調(diào)一點：用來循環(huán)中間點的變量k必須放在最外面一層循環(huán)?！纠?-1】、最短路徑問題【問題描述】平面上有n個點（n=100），每個點的坐標均在-1000010000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離?，F(xiàn)在的任務是找出從一點到另一點之間的最短路徑?！据斎敫袷健?輸入文件為short.in，共n+m+3行，其中: 第一行為整數(shù)n。 第2行到第n+1行（共n行） ，每行兩個整數(shù)x和y

5、，描述了一個點的坐標。 第n+2行為一個整數(shù)m，表示圖中連線的個數(shù)。 此后的m 行，每行描述一條連線，由兩個整數(shù)i和j組成，表示第i個點和第j個點之間有連線。 最后一行：兩個整數(shù)s和t，分別表示源點和目標點。 【輸出格式】 輸出文件為short.out，僅一行，一個實數(shù)（保留兩位小數(shù)），表示從s到t的最短路徑長度?！据斎霕永斎霕永? 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庫

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】牛的旅行牛的旅行【問題描述問題描述】農(nóng)民農(nóng)民JohnJohn的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個

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

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

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

11、 ( 0 = XY ( 0 = X，Y= Y= 100000 )100000 )， 表示表示N N個牧區(qū)的坐標。每個牧個牧區(qū)的坐標。每個牧區(qū)的坐標都是不一樣的。區(qū)的坐標都是不一樣的。 第第 N+2 N+2 行行到第到第 2 2* *N+1 N+1 行：每行包括行：每行包括N N個數(shù)字個數(shù)字 ( 0( 0或或1 ) 1 ) 表示一個對稱鄰接矩陣。表示一個對稱鄰接矩陣。 例如，例如，題目描述中的兩個牧場的矩陣描述如下：題目描述中的兩個牧場的矩陣描述如下： 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ù)中至少包括兩個不連通的牧區(qū)。輸入數(shù)據(jù)中至少包括兩個不連通的牧區(qū)?！据敵龈袷捷敵龈袷健?只有一行，

13、包括一個實數(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求出任兩點間的最短路，然后求出每個點到所有可達的點的最大距離，記做mdisi。（Floyed算法） r1=max(mdisi) 然后枚舉不連通的兩點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)用來計算從一個點到其他所有點的最短路徑的算法，是一種單源最短路徑算法。也就用來計算從一個點到其他所有點的最短路徑的算法，是一種單源最短路徑算法。也就是說，只能計算起點只有一個的情況。是說，只能計算起點只有一個的情況。Dijkstraijkstra的時間復雜度是的時間復雜度是O (N2)，它不能處理存在負邊權的情況。，它不能處理存在負邊權的情況。算法描述：算法描述： 設起點為設起點為s，disv表示從表示從s到到v的最短路徑，的最短路徑，prev為為v的前驅(qū)節(jié)點，用來輸出路徑。的前驅(qū)節(jié)點，

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

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

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

23、徑，就是把這個點由藍點變?yōu)?。如果我們要求出一個點的最短路徑，就是把這個點由藍點變?yōu)榘c。從起點到藍點的最短路徑上的中轉(zhuǎn)點在這個時刻只能是白點。白點。從起點到藍點的最短路徑上的中轉(zhuǎn)點在這個時刻只能是白點。 Dijkstra Dijkstra的算法思想，就是一開始將起點到起點的距離標記為的算法思想，就是一開始將起點到起點的距離標記為0，而后進行，而后進行n次循環(huán)，次循環(huán)，每次找出一個到起點距離每次找出一個到起點距離disu最短的點最短的點u，將它從藍點變?yōu)榘c。隨后枚舉所有的藍點，將它從藍點變?yōu)榘c。隨后枚舉所有的藍點vi，如果以此白點為中轉(zhuǎn)到達藍點如果以此白點為中轉(zhuǎn)到達藍點vi的路徑的路徑dis

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

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

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

27、3的最短路徑是的最短路徑是-2（123），但是），但是dijskstra在第二輪循環(huán)在第二輪循環(huán)開始時會找到當前開始時會找到當前disi最小的點最小的點3，并標記它為白點。，并標記它為白點。這時的這時的dis3=1，然而，然而1卻不是從起點到點卻不是從起點到點3的最短路徑。因為的最短路徑。因為3已被標記為白點，最短路徑值已被標記為白點，最短路徑值dis3不會再被修改了，所以我們在邊權存在負數(shù)的情況下得到了錯誤的答案！不會再被修改了，所以我們在邊權存在負數(shù)的情況下得到了錯誤的答案！12345213-4562【例例4-3】、最短路徑問題、最短路徑問題(Dijkstra) 題目參見題目參見“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+) / /查找可以更新的點查找可以更新的點 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】最小花費最小花費【問題描述問題描述】 在在n n個人中，某些人的銀行賬號之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費各不相同。個人中，某些人的銀行賬號之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費各不相同。給定這些人之間轉(zhuǎn)賬時需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費，請問給定這些人之間轉(zhuǎn)賬時需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費，請問A A最少需要多少錢使得最少需

31、要多少錢使得轉(zhuǎn)賬后轉(zhuǎn)賬后B B收到收到100100元。元?！据斎敫袷捷斎敫袷健?第一行輸入兩個正整數(shù)第一行輸入兩個正整數(shù)n,mn,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對數(shù)。，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對數(shù)。 以下以下m m行每行輸入三個正整數(shù)行每行輸入三個正整數(shù)x,y,zx,y,z，表示標號為，表示標號為x x的人和標號為的人和標號為y y的人之間互相轉(zhuǎn)賬需要扣的人之間互相轉(zhuǎn)賬需要扣除除z%z%的手續(xù)費的手續(xù)費 (z100)(z100)。 最后一行輸入兩個正整數(shù)最后一行輸入兩個正整數(shù)A,BA,B。數(shù)據(jù)保證。數(shù)據(jù)保證A A與與B B之間可以直接或間接地轉(zhuǎn)賬。之間可以直接或間接地轉(zhuǎn)賬?！?/p>

32、輸出格式輸出格式】 輸出輸出A A使得使得B B到賬到賬100100元最少需要的總費用。精確到小數(shù)點后元最少需要的總費用。精確到小數(shù)點后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)簡稱簡稱FordFord（福特）算法，同樣是用來計算從一個點到其他所有點的最短路徑的算（福特）算法，同樣是用來計算從一個點到其他所有點的最短路徑的算法，也是一種單源最短路徑算法。法，也是一種單源最短路徑算法。能夠處理存在負邊權的情況，但無法處理存在負權回路的情況（下文會有詳細說能夠處理存在負邊權的情況，但無法處理存在負權回路的情況（下文會有詳細說明）。明）。算法時間復雜度：算法時間復雜度：O(NE)，N是頂點數(shù)，是頂點數(shù)，E是邊數(shù)。是邊數(shù)。算法實現(xiàn)：算

36、法實現(xiàn)：設設s為起點，為起點，disv即為即為s到到v的最短距離，的最短距離，prev為為v前驅(qū)。前驅(qū)。wj是邊是邊j的長度，且的長度，且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+) / /注意要枚舉所有邊，不能枚舉點。注意要枚舉所有邊，不能枚舉點。 if ( (disu+wjdisv) ) /u /u、v分別是這條邊連接的兩個點。分別是這條邊連接的兩個點。 disv =disu + wj

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

38、ellman-Ford算法可以求出存在負邊權情況下的最短路徑，卻無法解決存在負權回算法可以求出存在負邊權情況下的最短路徑，卻無法解決存在負權回路的情況。路的情況。 負權回路是指邊權之和為負數(shù)的一條回路，上圖中負權回路是指邊權之和為負數(shù)的一條回路，上圖中- - - - -這條回路的邊權之和為這條回路的邊權之和為-3。在有負權回路的情況下，從在有負權回路的情況下，從1到到6的最短路徑是多少？答案是無窮小，因為我們可以繞這條負權回的最短路徑是多少？答案是無窮小，因為我們可以繞這條負權回路走無數(shù)圈，每走一圈路徑值就減去路走無數(shù)圈，每走一圈路徑值就減去3，最終達到無窮小。，最終達到無窮小。所以說存在負權

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

40、我們規(guī)定每條邊只能走一次，在這個前提下可以求出負權回路的最短路徑。這個問題就留待讀者自己思考（提示：對留待讀者自己思考（提示：對Floyed做一點小處理）。做一點小處理）。【例【例4-5】、最短路徑問題、最短路徑問題(Bellman-Ford) 題目參見題目參見“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) ) / /隊列中不存在隊列中不存在v v點，點，v v入隊。入隊。 / /尾指針下移一位，尾指針下移一位，v v入隊入隊; ; e existv=true;xistv=true; while (head tail); while (head tail);循環(huán)隊列：采用循環(huán)隊列能夠降低隊列大小，隊列長度只需開到2*n+5即可。例題中的參考程序使用了循環(huán)隊列?！纠?-6】、香甜的黃油、香甜的黃油(Sweet Butter) )【問題描述問題描述】農(nóng)夫農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛

43、州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道N（1=N=500）只奶牛會過來舔它，這樣就能做出能賣好價錢的超）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。甜黃油。當然，他將付出額外的費用在奶牛上。 農(nóng)夫農(nóng)夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至很狡猾。像以前的巴甫洛夫，他知道他可以訓練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠

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

45、2行到第行到第N+C+1行：每行有三個數(shù)：相連的牧場行：每行有三個數(shù)：相連的牧場A、B，兩牧場間距（，兩牧場間距（1=D=255），當然，連接是雙向的。），當然，連接是雙向的?！据敵龈袷捷敵龈袷健縝utter.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 / /說明：放

46、在說明：放在4號牧場最優(yōu)號牧場最優(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); / /隊列數(shù)組初始化隊列數(shù)組初始化 memset(exist,false,sizeof(exist); memset(exist,false,sizeof(exist); /exist /exist標志初始化標志初始化 disi=0;team1=i;head=0;tail=1;existi=true; disi=0;team1=i;head=0;tail=1;existi=true; / /起始點入隊起始點入隊 do do head+; head+; head=(head-1)%160

50、1)+1; head=(head-1)%1601)+1; / /循環(huán)隊列處理循環(huán)隊列處理 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都是單源最短路徑算法，它們的共同點是都都是單源最短路徑算法，它們的共同點是都有一個數(shù)組有一個數(shù)組prex 用來記錄從起點到用來記錄從起點到x的最短路徑中，的最短路徑中，x的前驅(qū)結(jié)點是哪個。的前驅(qū)結(jié)點是哪個。每次更新，我們就給每次更新，我們就給prex 賦一個新值，結(jié)合上面的思想講解，相信對于記錄賦一個新值，結(jié)合上面的思想講解，相信對于記錄某點的前驅(qū)結(jié)點是不難理解的。那么怎么利用某點的前驅(qū)結(jié)點是不難理解的。那么怎么利用prex 數(shù)組輸出最短路徑方案呢？數(shù)組輸出最短路徑方案呢？【例【例4-7】、最短路徑問題】、最短路徑問題(輸出路徑輸出路徑)要求改寫程序，用要求改寫程序，用Dijkstra、

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

54、 2.2.Floyed算法輸出最短路徑算法輸出最短路徑FloyedFloyed算法輸出路徑也是采用記錄前驅(qū)點的方式。因為算法輸出路徑也是采用記錄前驅(qū)點的方式。因為floyed是計算任意兩點是計算任意兩點間最短路徑的算法，間最短路徑的算法，disij記錄從記錄從i到到j的最短路徑值。故而我們定義的最短路徑值。故而我們定義preij為一個二維數(shù)組，記錄從為一個二維數(shù)組，記錄從i到到j的最短路徑中，的最短路徑中，j的前驅(qū)點是哪一個。的前驅(qū)點是哪一個?！纠?-8】、最短路徑問題、最短路徑問題(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,說明已經(jīng)遞歸到起點說明已經(jīng)遞歸到起點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 j的最短路徑更新為的最短路徑更新為i ik kj j，那么，那么i i到到j j最短路徑最短路徑j j的前驅(qū)就肯定與的前驅(qū)就肯定與k k到到j j最短路徑最短路徑j j的前驅(qū)相同。的前驅(qū)相同。 cout a; cout a; print(b); /a print(b); /a是起點，是起點，b b是

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

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