第4章第3-4節(jié) 圖論算法(C版)

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

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

3、離。在上圖中，因為dis13+dis32dis12，所以就用dis13+dis32來更新原先1到2的距離。我們在初始化時，把不相連的點之間的距離設為一個很大的數，不妨可以看作這兩點相隔很遠很遠，如果兩者之間有最短路徑的話，就會更新成最短路徑的長度。Floyed算法的時間復雜度是O(N3)。 1 2 3 216Floyed算法變形：如果是一個沒有邊權的圖，把相連的兩點間的距離設為disij=true，不相連的兩點設為disij=false，用Floyed算法的變形：For (k = 1; k = n; k+) For (i = 1; i = n; i+) For (j = 1; j = n; j

4、+) disij = disij | (disik & diskj); 用這個辦法可以判斷一張圖中的兩點是否相連。最后再強調一點：用來循環(huán)中間點的變量k必須放在最外面一層循環(huán)。【例4-1】、最短路徑問題【問題描述】平面上有n個點（n=100），每個點的坐標均在-1000010000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離?，F在的任務是找出從一點到另一點之間的最短路徑?！据斎敫袷健?輸入文件為short.in，共n+m+3行，其中: 第一行為整數n。 第2行到第n+1行（共n行） ，每行兩個整數x和y，描述了一個點的坐標。

5、 第n+2行為一個整數m，表示圖中連線的個數。 此后的m 行，每行描述一條連線，由兩個整數i和j組成，表示第i個點和第j個點之間有連線。 最后一行：兩個整數s和t，分別表示源點和目標點。 【輸出格式】 輸出文件為short.out，僅一行，一個實數（保留兩位小數），表示從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;double f101101;int n,

6、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數組為最大值 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 e; for (k = 1

7、; 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】牛的旅行【問題描述】農民John的農場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區(qū)不連通?，F在，John想在農場里添加一條路徑 ( 注意，恰好一條 )。對這條路徑有這樣的限制：一個牧

8、場的直徑就是牧場中最遠的兩個牧區(qū)的距離 ( 本題中所提到的所有距離指的都是最短的距離 )?？紤]如下的兩個牧場，圖是有5個牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。每一個牧區(qū)都有自己的坐標： 圖所示的牧場的直徑大約是12.07106, 最遠的兩個牧區(qū)是A和E，它們之間的最短路徑是A-B-E。 這兩個牧場都在John的農場上。John將會在兩個牧場中各選一個牧區(qū)，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認為它們是連通的。只有兩條路徑在同一個牧區(qū)相交，我們才認為它們是連通的。 現在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后

9、，這個更大的新牧場有最小的直徑?！据斎敫袷健?第 1 行：一個整數N (1 = N = 150), 表示牧區(qū)數； 第 2 到 N+1 行：每行兩個整數X，Y ( 0 = X，Y= 100000 )， 表示N個牧區(qū)的坐標。每個牧區(qū)的坐標都是不一樣的。 第 N+2 行到第 2*N+1 行：每行包括N個數字 ( 0或1 ) 表示一個對稱鄰接矩陣。 例如，題目描述中的兩個牧場的矩陣描述如下： A B C D E F G H A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 C 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

10、F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 輸入數據中至少包括兩個不連通的牧區(qū)?！据敵龈袷健?只有一行，包括一個實數，表示所求答案。數字保留六位小數?！据斎霕永?8 10 10 15 10 20 10 15 15 20 15 30 15 25 10 30 10 01000000 10111000 01001000 01001000 01110000 00000010 00000101 00000010【輸出樣例】 22.071068【算法分析】 用Floyed求出任兩點間的最短路，然后求出每個點到所有可達的點的最大距離，記做md

11、isi。（Floyed算法） r1=max(mdisi) 然后枚舉不連通的兩點i,j，把他們連通，則新的直徑是mdisi+mdisj+(i,j)間的距離。 r2=min(mdisi+mdisj+disi,j) re=max(r1,r2) re就是所求。【參考程序】#include#includeusing namespace std;double f151151,m151,minx,r,temp,x151,y151,maxint=1e12;double dist(int i,int j) return sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj) ; int main

12、() int i,j,n,k;char c; cinn; for(i=1;ixiyi; for(i=1;i=n;i+) for(j=1;jc; if(c=1)fij=dist(i,j); else fij=maxint; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(i!=j&i!=k&j!=k) if(fikmaxint-1&fkjfik+fkj) fij=fik+fkj; memset(m,0,sizeof(m); for(i=1;i=n;i+) for(j=1;j=n;j+) if(fijmaxint-1&mifij)mi=fij;

13、 minx=1e20; for(i=1;i=n;i+) for(j=1;jmaxint-1) temp=dist(i,j); if(minxmi+mj+temp)minx=mi+mj+temp; r=0; for(i=1;iminx)minx=mi; printf(%.6lf,minx); return 0;2.Dijkstra算法O (N2)用來計算從一個點到其他所有點的最短路徑的算法，是一種單源最短路徑算法。也就是說，只能計算起點只有一個的情況。Dijkstra的時間復雜度是O (N2)，它不能處理存在負邊權的情況。算法描述： 設起點為s，disv表示從s到v的最短路徑，prev為v的前驅

14、節(jié)點，用來輸出路徑。 a)初始化：disv=(vs); diss=0; pres=0; b)For (i = 1; i = n ; i+) 1.在沒有被訪問過的點中找一個頂點u使得disu是最小的。 2.u標記為已確定最短路徑 3.For 與u相連的每個未確定最短路徑的頂點v if (disu+wuv disv) disv = disu + wuv; prev = u; c)算法結束：disv為s到v的最短距離；prev為v的前驅節(jié)點，用來輸出路徑。算法分析&思想講解： 從起點到一個點的最短路徑一定會經過至少一個“中轉點”（例如下圖1到5的最短路徑，中轉點是2。特殊地，我們認為起點1也是一個“

15、中轉點”）。顯而易見，如果我們想求出起點到一個點的最短路徑，那我們必然要先求出中轉點的最短路徑（例如我們必須先求出點2 的最短路徑后，才能求出從起點到5的最短路徑）。中轉點終點最短路1101221、2331、2、3441、254 換句話說，如果起點1到某一點V0的最短路徑要經過中轉點Vi，那么中轉點Vi一定是先于V0被確定了最短路徑的點。 我們把點分為兩類，一類是已確定最短路徑的點，稱為“白點”，另一類是未確定最短路徑的點，稱為“藍點”。如果我們要求出一個點的最短路徑，就是把這個點由藍點變?yōu)榘c。從起點到藍點的最短路徑上的中轉點在這個時刻只能是白點。 Dijkstra的算法思想，就是一開始將起

16、點到起點的距離標記為0，而后進行n次循環(huán)，每次找出一個到起點距離disu最短的點u，將它從藍點變?yōu)榘c。隨后枚舉所有的藍點vi，如果以此白點為中轉到達藍點vi的路徑disu+wuvi更短的話，這將它作為vi的“更短路徑”disvi（此時還不確定是不是vi的最短路徑）。 就這樣，我們每找到一個白點，就嘗試著用它修改其他所有的藍點。中轉點先于終點變成白點，故每一個終點一定能夠被它的最后一個中轉點所修改，而求得最短路徑。123452471162求解順序讓我們對以上這段枯燥的文字做一番模擬，加深理解。 算法開始時，作為起點的dis1 = 0，其他的點disi = 0 x7fffffff。1234524

17、71162第一輪循環(huán)找到dis1最小，將1變成白點。對所有的藍點做出修改，使得dis2=2,dis3=4,dis4=7。這時dis2，dis3，dis4被它的最后一個中轉點1修改為了最短路徑。123452471162第二輪循環(huán)找到dis2最小，將2變成白點。對所有的藍點做出修改，使得dis3=3,dis5=4。這時dis3，dis5被它們的最后一個中轉點2修改為了最短路徑。123452471162第三輪循環(huán)找到dis3最小，將3變成白點。對所有的藍點做出修改，使得dis4=4。發(fā)現以3為中轉不能修改5，說明3不是5的最后一個中轉點。這時dis4也被它的最后一個中轉點3修改為了最短路徑。接下來的

18、兩輪循環(huán)將4、5也變成白點。N輪循環(huán)結束后，所有的點的最短路徑即能求出。Dijkstra無法處理邊權為負的情況，例如右圖這個例子。2到3的邊權值為-4，顯然從起點1到3的最短路徑是-2（123），但是dijskstra在第二輪循環(huán)開始時會找到當前disi最小的點3，并標記它為白點。這時的dis3=1，然而1卻不是從起點到點3的最短路徑。因為3已被標記為白點，最短路徑值dis3不會再被修改了，所以我們在邊權存在負數的情況下得到了錯誤的答案！12345213-4562【例4-3】、最短路徑問題(Dijkstra) 題目參見“Floyed算法”，但本題要求使用dijkstra算法解決。#includ

19、e#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(pow(double(ax1-ay1),2)+pow(double(ax2-a

20、y2),2); cin s e; for (i = 1; i = n; i+) ci = fsi; memset(b,false,sizeof(b); /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 = j; if (k = 0) break; bk = true; for (j = 1; j = n; j+) if (ck + fkj cj) cj =

21、 ck + fkj; printf(%.2lfn,ce); return 0;【例4-4】最小花費【問題描述】 在n個人中，某些人的銀行賬號之間可以互相轉賬。這些人之間轉賬的手續(xù)費各不相同。給定這些人之間轉賬時需要從轉賬金額里扣除百分之幾的手續(xù)費，請問A最少需要多少錢使得轉賬后B收到100元?！据斎敫袷健?第一行輸入兩個正整數n,m，分別表示總人數和可以互相轉賬的人的對數。 以下m行每行輸入三個正整數x,y,z，表示標號為x的人和標號為y的人之間互相轉賬需要扣除z%的手續(xù)費 (z100)。 最后一行輸入兩個正整數A,B。數據保證A與B之間可以直接或間接地轉賬?！据敵龈袷健?輸出A使得B到賬10

22、0元最少需要的總費用。精確到小數點后8位。【輸入樣例】 3 3 1 2 1 2 3 2 1 3 3 1 3【輸出樣例】 103.07153164【數據規(guī)?！?1=n=2000【參考程序】#includeusing namespace std;double a20012001,dis2001=0,minn;int n,m,i,j,k,x,y,f2001=0;void init() cinnm; for(i=1;ixy; void dijkstra(int x) for(i=1;i=n;i+)disi=axi; disx=1;fx=1; for(i=1;i=n-1;i+) minn=0; for(

23、j=1;jminn)k=j;minn=disj; fk=1; if(k=y)break; for(j=1;jdisj)disj=disk*akj; int main() init(); dijkstra(x); printf(%0.8lf,100/disy); return 0;3.Bellman-Ford算法O(NE)簡稱Ford（福特）算法，同樣是用來計算從一個點到其他所有點的最短路徑的算法，也是一種單源最短路徑算法。能夠處理存在負邊權的情況，但無法處理存在負權回路的情況（下文會有詳細說明）。算法時間復雜度：O(NE)，N是頂點數，E是邊數。算法實現：設s為起點，disv即為s到v的最短距

24、離，prev為v前驅。wj是邊j的長度，且j連接u、v。初始化：diss=0,disv=（vs），pres=0For (i = 1; i = n-1; i+)For (j = 1; j = E; j+) /注意要枚舉所有邊，不能枚舉點。 if (disu+wjdisv) /u、v分別是這條邊連接的兩個點。 disv =disu + wj; prev = u; 算法分析&思想講解：Bellman-Ford算法的思想很簡單。一開始認為起點是白點(dis1=0)，每一次都枚舉所有的邊，必然會有一些邊，連接著白點和藍點。因此每次都能用所有的白點去修改所有的藍點，每次循環(huán)也必然會有至少一個藍點變成白點。

25、在上面這個簡單的模擬中能看到白點的“蔓延”情況。負權回路：雖然Bellman-Ford算法可以求出存在負邊權情況下的最短路徑，卻無法解決存在負權回路的情況。 負權回路是指邊權之和為負數的一條回路，上圖中-這條回路的邊權之和為-3。在有負權回路的情況下，從1到6的最短路徑是多少？答案是無窮小，因為我們可以繞這條負權回路走無數圈，每走一圈路徑值就減去3，最終達到無窮小。所以說存在負權回路的圖無法求出最短路徑，Bellman-Ford算法可以在有負權回路的情況下輸出錯誤提示。 如果在Bellman-Ford算法的兩重循環(huán)完成后，還是存在某條邊使得：disu+wdisv，則存在負權回路：For每條邊(

26、u,v) If (disu+wdisv) return False如果我們規(guī)定每條邊只能走一次，在這個前提下可以求出負權回路的最短路徑。這個問題就留待讀者自己思考（提示：對Floyed做一點小處理）?！纠?-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; for (in

27、t i=1;im; for (int i=1;i=m;i+) /初始化數組dis，f disi=0 x7fffffff/3; fi1 = fi2 = 0 x7fffffff/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+wuv) disv=disu+wuv; prev=u; if (!existv) /隊列中不存在v點，v入隊。 /尾指針下移一位，v入隊; existv=tr

28、ue; while (head tail);循環(huán)隊列：采用循環(huán)隊列能夠降低隊列大小，隊列長度只需開到2*n+5即可。例題中的參考程序使用了循環(huán)隊列?！纠?-6】、香甜的黃油(Sweet Butter)【問題描述】農夫John發(fā)現做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道N（1=N=500）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。 農夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。農夫John知道每只奶牛都在各自喜歡的牧場

29、（一個牧場不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路線，找出使所有牛到達的路程和最短的牧場（他將把糖放在那）。 【輸入格式】butter.in第一行: 三個數：奶牛數N，牧場數P（2=P=800），牧場間道路數C(1=C=1450)。第二行到第N+1行: 1到N頭奶牛所在的牧場號。第N+2行到第N+C+1行：每行有三個數：相連的牧場A、B，兩牧場間距（1=D=255），當然，連接是雙向的?！据敵龈袷健縝utter.out 一行 輸出奶牛必須行走的最小的距離和.【輸入樣例】3 4 52341 2 11 3 52 3 72 4 33 4 5樣例圖形 P2 P1 -1- C1 | | 5 7

30、 3 | | C3 C2 -5- P3 P4【輸出樣例】8 /說明：放在4號牧場最優(yōu)【參考程序】#include#include#includeusing namespace std;int n,p,c,i,j,x,y,t,min1,head,tail,tot,u;int a801801,b501,dis801,num801,w801801,team1601;bool exist801;int main() freopen(butter.in,r,stdin); freopen(butter.out,w,stdout); cinnpc; for(i=1;i=p;i+) bi=0; numi=0

31、; for(j=1;j=p;j+) wij=0 x7fffffff/3; for(i=1;ibi; for(i=1;ixyt; wxy=t; ax+numx=y; ay+numy=x; wyx=wxy; min1=0 x7fffffff/3; for(i=1;i=p;i+) for(j=1;j=p;j+) disj=0 x7fffffff/3; memset(team,0,sizeof(team); /隊列數組初始化 memset(exist,false,sizeof(exist); /exist標志初始化 disi=0;team1=i;head=0;tail=1;existi=true; /

32、起始點入隊 do head+; head=(head-1)%1601)+1; /循環(huán)隊列處理 u=teamhead; existu=false; for(j=1;jdisu+wuauj) disauj=disu+wuauj; if (!existauj) tail+; tail=(tail-1)%1601)+1; teamtail=auj; existauj=true; while(head!=tail); tot=0; for(j=1;j=n;j+) tot+=disbj; if (totmin1) min1=tot; coutmin1; return 0;二、輸出最短路徑1.單源最短路徑的

33、輸出Dijkstra，Bellman-Ford，SPFA都是單源最短路徑算法，它們的共同點是都有一個數組prex 用來記錄從起點到x的最短路徑中，x的前驅結點是哪個。每次更新，我們就給prex賦一個新值，結合上面的思想講解，相信對于記錄某點的前驅結點是不難理解的。那么怎么利用prex數組輸出最短路徑方案呢？【例4-7】、最短路徑問題(輸出路徑)要求改寫程序，用Dijkstra、Bellman-Ford、SPFA算法輸出最短路徑的方案。使用一個小小的遞歸過程就能解決這一問題。void print(int x) if (preax = 0) return; /起點的前驅我們已設為0print(pr

34、eax); cout x; /主程序中：main（進行Dijkstra或Bellman-Ford，SPFA運算）cout s; print(e); /s是起點，e是終點2.Floyed算法輸出最短路徑Floyed算法輸出路徑也是采用記錄前驅點的方式。因為floyed是計算任意兩點間最短路徑的算法，disij記錄從i到j的最短路徑值。故而我們定義preij為一個二維數組，記錄從i到j的最短路徑中，j的前驅點是哪一個?！纠?-8】、最短路徑問題(Floyed法輸出路徑)要求改寫Floyed的程序，模仿Dijkstra輸出路徑的方法用floyed輸出最短路徑方案?！緟⒖汲绦颉?include#inc

35、lude#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; /preaa=0,說明已經遞歸到起點a print(preax); cout n; for (i = 1; i xi yi; memset(dis,0 x7f,sizeof(dis); /初始化數組 cin m; memset(pre,0,sizeof(pre); /初始化前驅

36、數組 for (i = 1; i a b; disab = disba = sqrt(pf(xa-xb)+pf(ya-yb); preab = a; /a與b相連，自然從a到b的最短路徑b的前驅是a preba = b; cin a b; for (k = 1; k = n; k+) /floyed 最短路 for (i = 1; i = n; i+) for (j = 1; j disik+diskj) disij = disik + diskj; preij = prekj; /從i到j的最短路徑更新為ikj，那么i到j最短路徑j的前驅就肯定與k到j最短路徑j的前驅相同。 cout a;

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

38、，送信才算成功。因為準備充足，每個哨所內都安排了足夠的信使（如果一個哨所與其他k個哨所有通信聯(lián)系的話，這個哨所內至少會配備k個信使）。 現在總指揮請你編一個程序，計算出完成整個送信過程最短需要多少時間?！据斎敫袷健?輸入文件msner.in，第1行有兩個整數n和m，中間用1個空格隔開，分別表示有n個哨所和m條通信線路。1=n=100。 第2至m+1行：每行三個整數i、j、k，中間用1個空格隔開，表示第i個和第j個哨所之間存在通信線路，且這條線路要花費k天?！据敵龈袷健?輸出文件msner.out，僅一個整數，表示完成整個送信過程的最短時間。如果不是所有的哨所都能收到信，就輸出-1?！据斎霕永?/p>

39、 4 4 1 2 4 2 3 7 2 4 1 3 4 6【輸出樣例】 112、最優(yōu)乘車【問題描述】 H城是一個旅游勝地，每年都有成千上萬的人前來觀光。為方便游客，巴士公司在各個旅游景點及賓館，飯店等地都設置了巴士站并開通了一些單程巴上線路。每條單程巴士線路從某個巴士站出發(fā)，依次途經若干個巴士站，最終到達終點巴士站。 一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士, 這樣換乘幾次后到達S公園。 現在用整數1,2,N 給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號為1，S公園

40、巴士站的編號為N。 寫一個程序，幫助這名旅客尋找一個最優(yōu)乘車方案,使他在從飯店乘車到S公園的過程中換車的次數最少?！据斎敫袷健?輸入文件是Travel.in。文件的第一行有兩個數字M和N(1=M=100 1N=500），表示開通了M條單程巴士線路，總共有N個車站。從第二行到第M刊行依次給出了第1條到第M條巴士線路的信息。其中第i+1行給出的是第i條巴士線路的信息，從左至右按運行順序依次給出了該線路上的所有站號相鄰兩個站號之間用一個空格隔開?！据敵龈袷健?輸出文件是Travel.out，文件只有一行。如果無法乘巴士從飯店到達S公園，則輸出NO，否則輸出你的程序所找到的最少換車次數，換車次數為0表

41、示不需換車即可到達?！据斎霕永縏ravel.in3 76 74 7 3 62 1 3 5【輸出樣例】Travel.out23、最短路徑【問題描述】給出一個有向圖G=(V, E)，和一個源點v0V，請寫一個程序輸出v0和圖G中其它頂點的最短路徑。只要所有的有向環(huán)都是正的，我們就允許圖的邊有負值。頂點的標號從1到n（n為圖G的頂點數）?！据斎敫袷健康?行：一個正數n（2=n 2) = 2 (1 - 3) = 5 (1 - 4) = 9 (1 - 5) = 9樣例所對應的圖如下:第四節(jié) 圖的連通性問題一、判斷圖中的兩點是否連通1、Floyed算法時間復雜度：O(N3 )算法實現：把相連的兩點間的距

42、離設為disij=true,不相連的兩點設為disij=false，用Floyed算法的變形：for (k = 1; k = n; k+) for (i = 1; i = n; i+) for (j = 1; j = n; j+) disij = disij | (disik & diskj);最后如果disij=true的話，那么就說明兩點之間有路徑連通。有向圖與無向圖都適用。2、遍歷算法時間復雜度：O(N2 )算法實現：從任意一個頂點出發(fā)，進行一次遍歷，能夠從這個點出發(fā)到達的點就與起點是聯(lián)通的。這樣就可以求出此頂點和其它各個頂點的連通情況。所以只要把每個頂點作為出發(fā)點都進行一次遍歷，就能知

43、道任意兩個頂點之間是否有路存在?？梢允褂肈FS實現。有向圖與無向圖都適用。二、最小環(huán)問題最小環(huán)就是指在一張圖中找出一個環(huán)，使得這個環(huán)上的各條邊的權值之和最小。在Floyed的同時，可以順便算出最小環(huán)。記兩點間的最短路為disij，gij為邊的權值。for (k = 1; k = n; k+) for (i = 1; i = k-1; i+) for (j = i+1; j = k-1; j+) answer = min(answer,disij+gjk+gki); for (i = 1; i = n; i+) for (j = 1; j = n; j+) disij=min(disij,disik+diskj); answer即為這張圖的最小環(huán)。一個環(huán)中的最大結點為k(編號最大)，與它相連的兩個點為i,j，這個環(huán)的最短長度為gik+gkj+(i到j的路徑中,所有結點編號都小于k的最短路徑長度)。根據Floyed的原理，在最外層循環(huán)做了k-1次之后，disij則代表了i到j的路徑中，所有結點編號都小于k的最短路徑。綜上所述，該算法一定能找到圖中最小環(huán)。三、求有向圖的強連通分量 Kosaraju算法可以求出有向圖中的強連通分量個數，并且對分屬于不同強連