c++編程入門第六次課

六、圖論王振昊第一節(jié)基本概念一、什么是圖？很簡單，點用邊連起來就叫做圖，嚴格意義上講，圖是一種數(shù)據(jù)結(jié)構(gòu)，定義為：graph=（V，E）。V是一個非空有限集合，代表頂點（結(jié)點），E代表邊的集合。二、圖的一些定義和概念(a)有向圖：圖的邊有方向，只能按箭頭方向從一點到另一點。(a)就是一個有向圖。(b)無向圖：圖的邊沒有方向，可以雙向。(b)就是一個無向圖。結(jié)點的度：無向圖中與結(jié)點相連的邊的數(shù)目，稱為結(jié)點的度。結(jié)點的入度：在有向圖中，以這個結(jié)點為終點的有向邊的數(shù)目。結(jié)點的出度：在有向圖中，以這個結(jié)點為起點的有向邊的數(shù)目。權(quán)值：邊的“費用”，可以形象地理解為邊的長度。連通：如果圖中結(jié)點U，V之間存在一條從U通過若干條邊、點到達V的通路，則稱U、V是連通的?；芈罚浩瘘c和終點相同的路徑，稱為回路，或“環(huán)”。完全圖：一個n階的完全無向圖含有n*(n-1)/2條邊；一個n階的完全有向圖含有n*(n-1)條邊；稠密圖：一個邊數(shù)接近完全圖的圖。稀疏圖：一個邊數(shù)遠遠少于完全圖的圖。

強連通分量：有向圖中任意兩點都連通的最大子圖。右圖中，1-2-5構(gòu)成一個強連通分量。特殊地，單個點也算一個強連通分量，所以右圖有三個強連通分量：1-2-5，4，3。12345(a)12345(b)12345

三、圖的存儲結(jié)構(gòu)1.二維數(shù)組鄰接矩陣存儲定義intG[101][101];G[i][j]的值，表示從點i到點j的邊的權(quán)值，定義如下：

上圖中的3個圖對應(yīng)的鄰接矩陣分別如下：0111011∞58∞3G（A）=1011G（B）=0015∞2∞61100010G（C）=82∞1041100∞∞10∞1136411∞下面是建立圖的鄰接矩陣的參考程序段：#include<iostream>usingnamespacestd;inti,j,k,e,n;doubleg[101][101];doublew;intmain(){inti,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=0x7fffffff（賦一個超大值）;//初始化，對于不帶權(quán)的圖g[i][j]=0，表示沒有邊連通。這里用0x7fffffff代替無窮大。cin>>e;for(k=1;k<=e;k++){cin>>i>>j>>w;//讀入兩個頂點序號及權(quán)值g[i][j]=w;//對于不帶權(quán)的圖g[i][j]=1g[j][i]=w;//無向圖的對稱性,如果是有向圖則不要有這句！}…………return0;}建立鄰接矩陣時，有兩個小技巧:初始化數(shù)組大可不必使用兩重for循環(huán)。1)如果是int數(shù)組，采用memset(g,0x7f,sizeof(g))可全部初始化為一個很大的數(shù)(略小于0x7fffffff)，使用memset(g,0,sizeof(g))，全部清為0，使用memset(g,0xaf,sizeof(g))，全部初始化為一個很小的數(shù)。2)如果是double數(shù)組，采用memset(g,127,sizeof(g));可全部初始化為一個很大的數(shù)1.38*10306，使用memset(g,0,sizeof(g))全部清為0.2.數(shù)組模擬鄰接表存儲圖的鄰接表存儲法，又叫鏈式存儲法。本來是要采用鏈表實現(xiàn)的，但大多數(shù)情況下只要用數(shù)組模擬即可。定義兩個數(shù)組，例如：intg[101][101];用來存儲這個圖。再定義一個一維數(shù)組：intnum[101];用來記錄與每個點相連的點的數(shù)目。如果邊有權(quán)值，還要定義一個數(shù)組intval[101][101]存儲邊權(quán)。以下是用數(shù)組模擬鄰接表存儲的參考程序段：#include<iostream>usingnamespacestd;intn,m,i,j,c;intg[101][101];intnum[101];intmain(){memset(g,0x7f,sizeof(g));memset(num,0,sizeof(num));cin>>n;for(i=1;i<=n;i++){cin>>num[i];//第i行說明點i的連接情況，每行的開頭讀入與之相連的點的數(shù)目for(j=1;j<=num[i];j++){cin>>g[i][j];//第j個與i相連的點是g[i][j]val[i][g[i][j]]=v;//有權(quán)圖還要存下權(quán)值}}…………return0;}兩種方法各有用武之地，需按具體情況，具體選用。第二節(jié)圖的遍歷一、深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點出發(fā)系統(tǒng)地訪問圖中所有頂點，使每個頂點恰好被訪問一次，這種運算操作被稱為圖的遍歷。為了避免重復(fù)訪問某個頂點，可以設(shè)一個標志數(shù)組visited[i]，未訪問時值為false，訪問一次后就改為true。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法，兩者的時間效率都是O(n*n)。1.深度優(yōu)先遍歷深度優(yōu)先遍歷與深搜DFS相似，從一個點A出發(fā)，將這個點標為已訪問visited[i]:=true;，然后再訪問所有與之相連，且未被訪問過的點。當A的所有鄰接點都被訪問過后，再退回到A的上一個點（假設(shè)是B），再從B的另一個未被訪問的鄰接點出發(fā)，繼續(xù)遍歷。例如對右邊的這個無向圖深度優(yōu)先遍歷，假定先從1出發(fā)程序以如下順序遍歷：

1→2→5，然后退回到2，退回到1。從1開始再訪問未被訪問過的點3，3沒有未訪問的鄰接點，退回1。再從1開始訪問未被訪問過的點4，再退回1。起點1的所有鄰接點都已訪問，遍歷結(jié)束。12345下面給出的深度優(yōu)先遍歷的參考程序，假設(shè)圖以鄰接表存儲voiddfs(inti)//圖用數(shù)組模擬鄰接表存儲，訪問點i{visited[i]=true;//標記為已經(jīng)訪問過for(intj=1;j<=num[i];j++)//遍歷與i相關(guān)聯(lián)的所有未訪問過的頂點if(!visited[g[i][j]])dfs(g[i][j]);}主程序如下:intmain(){……memset(visited,false,sizeof(visited));for(inti=1;i<=n;i++)//每一個點都作為起點嘗試訪問，因為不是從任何//一點開始都能遍歷整個圖的，例如下面的兩個圖。if(!visited[i])dfs(i);……return0;}12345以3為起點根本不能遍歷整個圖這個非連通無向圖任何一個點為起點都不能遍歷整個圖145232.廣度優(yōu)先遍歷廣度優(yōu)先遍歷并不常用，從編程復(fù)雜度的角度考慮，通常采用的是深度優(yōu)先遍歷。廣度優(yōu)先遍歷和廣搜BFS相似，因此使用廣度優(yōu)先遍歷一張圖并不需要掌握什么新的知識，在原有的廣度優(yōu)先搜索的基礎(chǔ)上，做一點小小的修改，就成了廣度優(yōu)先遍歷算法。二、一筆畫問題

如果一個圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果最后又回到起點，那這個路徑叫做歐拉回路。我們定義奇點是指跟這個點相連的邊數(shù)目有奇數(shù)個的點。對于能夠一筆畫的圖，我們有以下兩個定理。定理1：存在歐拉路的條件：圖是連通的，有且只有2個奇點。定理2：存在歐拉回路的條件：圖是連通的，有0個奇點。兩個定理的正確性是顯而易見的，既然每條邊都要經(jīng)過一次，那么對于歐拉路，除了起點和終點外，每個點如果進入了一次，顯然一定要出去一次，顯然是偶點。對于歐拉回路，每個點進入和出去次數(shù)一定都是相等的，顯然沒有奇點。求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對一個奇點執(zhí)行DFS，時間復(fù)雜度為O(m+n)，m為邊數(shù)，n是點數(shù)。以下是尋找一個圖的歐拉路的算法實現(xiàn)：樣例輸入:第一行n，m，有n個點，m條邊，以下m行描述每條邊連接的兩點。

551223344551樣例輸出:歐拉路或歐拉回路

154321【參考程序】Euler.cpp#include<iostream>#include<cstring>usingnamespacestd;#definemaxn101intg[maxn][maxn];//此圖用鄰接矩陣存儲intdu[maxn];//記錄每個點的度，就是相連的邊的數(shù)目intcircuit[maxn];//用來記錄找到的歐拉路的路徑intn,e,circuitpos,i,j,x,y,start;voidfind_circuit(inti)//這個點深度優(yōu)先遍歷過程尋找歐拉路{intj;for(j=1;j<=n;j++)if(g[i][j]==1)//從任意一個與它相連的點出發(fā){g[j][i]=g[i][j]=0;find_circuit(j);}circuit[++circuitpos]=i;//記錄下路徑}intmain(){memset(g,0,sizeof(g));cin>>n>>e;for(i=1;i<=e;i++){cin>>x>>y;g[y][x]=g[x][y]=1;du[x]++;//統(tǒng)計每個點的度du[y]++;}start=1;//如果有奇點，就從奇點開始尋找，這樣找到的就是for(i=1;i<=n;i++)//歐拉路。沒有奇點就從任意點開始，if(du[i]%2==1)//這樣找到的就是歐拉回路。(因為每一個點都是偶點)start=i;circuitpos=0;find_circuit(start);for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<'';cout<<endl;return0;}注意以上程序具有一定的局限性，對于下面這種情況它不能很好地處理：上圖具有多個歐拉回路，而本程序只能找到一個回路。讀者在遇到具體問題時，還應(yīng)對程序作出相應(yīng)的修改。三、哈密爾頓環(huán)歐拉回路是指不重復(fù)地走過所有路徑的回路，而哈密爾頓環(huán)是指不重復(fù)地走過所有的點，并且最后還能回到起點的回路。使用簡單的深度優(yōu)先搜索，就能求出一張圖中所有的哈密爾頓環(huán)。下面給出一段參考程序：#include<iostream>#include<cstring>usingnamespacestd;intstart,length,x,n;boolvisited[101],v1[101];intans[101],num[101];intg[101][101];voidprint(){inti;for(i=1;i<=length;i++)cout<<''<<ans[i];cout<<endl;}voiddfs(intlast,inti)//圖用數(shù)組模擬鄰接表存儲，訪問點i，last表示上次訪問的點{visited[i]=true;//標記為已經(jīng)訪問過v1[i]=true;//標記為已在一張圖中出現(xiàn)過ans[++length]=i;//記錄下答案for(intj=1;j<=num[i];j++){if(g[i][j]==x&&g[i][j]!=last)//回到起點，構(gòu)成哈密爾頓環(huán){ ans[++length]=g[i][j];print();//這里說明找到了一個環(huán)，則輸出ans數(shù)組。 length--; break; }if(!visited[g[i][j]])dfs(i,g[i][j]);//遍歷與i相關(guān)聯(lián)的所有未訪問過的頂點}length--;visited[i]=false;//這里是回溯過程，注意v1的值不恢復(fù)。}intmain(){memset(visited,false,sizeof(visited));memset(v1,false,sizeof(v1));for(x=1;x<=n;x++)//每一個點都作為起點嘗試訪問，因為不是從任何一點開始都能找過整個圖的if(!v1[x])//如果點x不在之前曾經(jīng)被訪問過的圖里。{length=0;//定義一個ans數(shù)組存答案，length記答案的長度。dfs(x);}return0;}第三節(jié)最短路徑算法如下圖所示，我們把邊帶有權(quán)值的圖稱為帶權(quán)圖。邊的權(quán)值可以理解為兩點之間的距離。一張圖中任意兩點間會有不同的路徑相連。最短路徑就是指連接兩點的這些路徑中最短的一條。

我們有四種算法可以有效地解決最短路徑問題。有一點需要讀者特別注意：邊的權(quán)值可以為負。當出現(xiàn)負邊權(quán)時，有些算法不適用。一、求出最短路徑的長度以下沒有特別說明的話，dis[u][v]表示從u到v最短路徑長度，w[u][v]表示連接u，v的邊的長度。1.Floyed-Warshall算法O(N3)簡稱Floyed(弗洛伊德)算法，是最簡單的最短路徑算法，可以計算圖中任意兩點間的最短路徑。Floyed的時間復(fù)雜度是O(N3)，適用于出現(xiàn)負邊權(quán)的情況。算法描述：初始化：點u、v如果有邊相連，則dis[u][v]=w[u][v]。如果不相連則dis[u][v]=0x7fffffffFor(k=1;k<=n;k++)For(i=1;i<=n;i++) For(j=1;j<=n;j++) If(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];算法結(jié)束：dis[i][j]得出的就是從i到j(luò)的最短路徑。算法分析&思想講解：三層循環(huán)，第一層循環(huán)中間點k，第二第三層循環(huán)起點終點i、j，算法的思想很容易理解：如果點i到點k的距離加上點k到點j的距離小于原先點i到點j的距離，那么就用這個更短的路徑長度來更新原先點i到點j的距離。在上圖中，因為dis[1][3]+dis[3][2]<dis[1][2]，所以就用dis[1][3]+dis[3][2]來更新原先1到2的距離。我們在初始化時，把不相連的點之間的距離設(shè)為一個很大的數(shù)，不妨可以看作這兩點相隔很遠很遠，如果兩者之間有最短路徑的話，就會更新成最短路徑的長度。Floyed算法的時間復(fù)雜度是O(N3)。123216Floyed算法變形：如果是一個沒有邊權(quán)的圖，把相連的兩點間的距離設(shè)為dis[i][j]=true，不相連的兩點設(shè)為dis[i][j]=false，用Floyed算法的變形：For(k=1;k<=n;k++)For(i=1;i<=n;i++)For(j=1;j<=n;j++)dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);用這個辦法可以判斷一張圖中的兩點是否相連。最后再強調(diào)一點：用來循環(huán)中間點的變量k必須放在最外面一層循環(huán)?！纠?-1】、最短路徑問題【問題描述】平面上有n個點（n<=100），每個點的坐標均在-10000~10000之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離?，F(xiàn)在的任務(wù)是找出從一點到另一點之間的最短路徑?！据斎敫袷健枯斎胛募閟hort.in，共n+m+3行，其中:第一行為整數(shù)n。第2行到第n+1行（共n行），每行兩個整數(shù)x和y，描述了一個點的坐標。第n+2行為一個整數(shù)m，表示圖中連線的個數(shù)。此后的m行，每行描述一條連線，由兩個整數(shù)i和j組成，表示第i個點和第j個點之間有連線。最后一行：兩個整數(shù)s和t，分別表示源點和目標點?！据敵龈袷健枯敵鑫募閟hort.out，僅一行，一個實數(shù)（保留兩位小數(shù)），表示從s到t的最短路徑長度?！据斎霕永?00202202315121314253515【輸出樣例】3.41【參考程序】#include<cstdio>#include<iostream>#include<cmath>#include<cstring>usingnamespacestd;inta[101][3];doublef[101][101];intn,i,j,k,x,y,m,s,e;intmain(){freopen("short.in","r",stdin);freopen("short.out","w",stdout);cin>>n;for(i=1;i<=n;i++)cin>>a[i][1]>>a[i][2];cin>>m;memset(f,0x7f,sizeof(f));//初始化f數(shù)組為最大值

for(i=1;i<=m;i++)//預(yù)處理出x、y間距離{cin>>x>>y;f[y][x]=f[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));//pow(x,y)表示x^y，其中x,y必須為double類型，要用cmath庫}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)&&(f[i][k]+f[k][j]<f[i][j]))f[i][j]=f[i][k]+f[k][j];printf("%.2lf\n",f[s][e]);return0;}【例4-2】牛的旅行【問題描述】農(nóng)民John的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區(qū)不連通?，F(xiàn)在，John想在農(nóng)場里添加一條路徑(注意，恰好一條)。對這條路徑有這樣的限制：一個牧場的直徑就是牧場中最遠的兩個牧區(qū)的距離(本題中所提到的所有距離指的都是最短的距離)?？紤]如下的兩個牧場，圖１是有5個牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。每一個牧區(qū)都有自己的坐標：圖１所示的牧場的直徑大約是12.07106,最遠的兩個牧區(qū)是A和E，它們之間的最短路徑是A-B-E。這兩個牧場都在John的農(nóng)場上。John將會在兩個牧場中各選一個牧區(qū)，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認為它們是連通的。只有兩條路徑在同一個牧區(qū)相交，我們才認為它們是連通的?，F(xiàn)在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，這個更大的新牧場有最小的直徑?！据斎敫袷健康?行：一個整數(shù)N(1<=N<=150),表示牧區(qū)數(shù)；第2到N+1行：每行兩個整數(shù)X，Y(0<=X，Y<=100000)，表示N個牧區(qū)的坐標。每個牧區(qū)的坐標都是不一樣的。第N+2行到第2*N+1行：每行包括N個數(shù)字(0或1)表示一個對稱鄰接矩陣。例如，題目描述中的兩個牧場的矩陣描述如下：ABCDEFGH

A01000000

B10111000

C01001000

D01001000

E01110000

F00000010

G00000101

H00000010

輸入數(shù)據(jù)中至少包括兩個不連通的牧區(qū)?！据敵龈袷健恐挥幸恍?，包括一個實數(shù)，表示所求答案。數(shù)字保留六位小數(shù)?！据斎霕永?/p>

8

1010

1510

2010

1515

2015

3015

2510

3010

01000000

10111000

01001000

01001000

01110000

00000010

00000101

00000010【輸出樣例】

22.071068【算法分析】用Floyd求出任兩點間的最短路，然后求出每個點到所有可達的點的最大距離，記做mdis[i]。（Floyd算法）r1=max(mdis[i])然后枚舉不連通的兩點i,j，把他們連通，則新的直徑是mdis[i]+mdis[j]+(i,j)間的距離。r2=min(mdis[i]+mdis[j]+dis[i,j])re=max(r1,r2)re就是所求?！緟⒖汲绦颉?include<iostream>#include<cmath>usingnamespacestd;doublef[151][151],m[151],minx,r,temp,x[151],y[151],maxint=1e12;doubledist(inti,intj){returnsqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}intmain(){inti,j,n,k;charc;cin>>n;for(i=1;i<=n;i++)cin>>x[i]>>y[i];for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>c;if(c=='1')f[i][j]=dist(i,j);elsef[i][j]=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(f[i][k]<maxint-1&&f[k][j]<maxint-1)if(f[i][j]>f[i][k]+f[k][j])f[i][j]=f[i][k]+f[k][j];

memset(m,0,sizeof(m));for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]<maxint-1&&m[i]<f[i][j])m[i]=f[i][j];minx=1e20;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=j&&f[i][j]>maxint-1){temp=dist(i,j);if(minx>m[i]+m[j]+temp)minx=m[i]+m[j]+temp;}r=0;for(i=1;i<=n;i++)if(m[i]>minx)minx=m[i];printf("%.6lf",minx);return0;}2.Dijkstra算法O(N2)用來計算從一個點到其他所有點的最短路徑的算法，是一種單源最短路徑算法。也就是說，只能計算起點只有一個的情況。Dijkstra的時間復(fù)雜度是O(N2)，它不能處理存在負邊權(quán)的情況。算法描述：

設(shè)起點為s，dis[v]表示從s到v的最短路徑，pre[v]為v的前驅(qū)節(jié)點，用來輸出路徑。

a)初始化：dis[v]=∞(v≠s);dis[s]=0;pre[s]=0;

b)For(i=1;i<=n;i++)1.在沒有被訪問過的點中找一個頂點u使得dis[u]是最小的。

2.u標記為已確定最短路徑

3.For與u相連的每個未確定最短路徑的頂點vif(dis[u]+w[u][v]

<

dis[v])

{dis[v]

=

dis[u]

+

w[u][v];pre[v]

=

u;

}

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

換句話說，如果起點1到某一點V0的最短路徑要經(jīng)過中轉(zhuǎn)點Vi，那么中轉(zhuǎn)點Vi一定是先于V0被確定了最短路徑的點。我們把點分為兩類，一類是已確定最短路徑的點，稱為“白點”，另一類是未確定最短路徑的點，稱為“藍點”。如果我們要求出一個點的最短路徑，就是把這個點由藍點變?yōu)榘c。從起點到藍點的最短路徑上的中轉(zhuǎn)點在這個時刻只能是白點。Dijkstra的算法思想，就是一開始將起點到起點的距離標記為0，而后進行n次循環(huán)，每次找出一個到起點距離dis[u]最短的點u，將它從藍點變?yōu)榘c。隨后枚舉所有的藍點vi，如果以此白點為中轉(zhuǎn)到達藍點vi的路徑dis[u]+w[u][vi]更短的話，這將它作為vi的“更短路徑”dis[vi]（此時還不確定是不是vi的最短路徑）。就這樣，我們每找到一個白點，就嘗試著用它修改其他所有的藍點。中轉(zhuǎn)點先于終點變成白點，故每一個終點一定能夠被它的最后一個中轉(zhuǎn)點所修改，而求得最短路徑。123452471162求解順序讓我們對以上這段枯燥的文字做一番模擬，加深理解。算法開始時，作為起點的dis[1]

=

0，其他的點dis[i]

=

0x7fffffff。123452471162第一輪循環(huán)找到dis[1]最小，將1變成白點。對所有的藍點做出修改，使得dis[2]=2,dis[3]=4,dis[4]=7。這時dis[2]，dis[3]，dis[4]被它的最后一個中轉(zhuǎn)點1修改為了最短路徑。123452471162第二輪循環(huán)找到dis[2]最小，將2變成白點。對所有的藍點做出修改，使得dis[3]=3,dis[5]=4。這時dis[3]，dis[5]被它們的最后一個中轉(zhuǎn)點2修改為了最短路徑。123452471162第三輪循環(huán)找到dis[3]最小，將3變成白點。對所有的藍點做出修改，使得dis[4]=4。發(fā)現(xiàn)以3為中轉(zhuǎn)不能修改5，說明3不是5的最后一個中轉(zhuǎn)點。這時dis[4]也被它的最后一個中轉(zhuǎn)點3修改為了最短路徑。接下來的兩輪循環(huán)將4、5也變成白點。N輪循環(huán)結(jié)束后，所有的點的最短路徑即能求出。Dijkstra無法處理邊權(quán)為負的情況，例如右圖這個例子。2到3的邊權(quán)值為-4，顯然從起點1到3的最短路徑是-2（1→2→3），但是dijskstra在第二輪循環(huán)開始時會找到當前dis[i]最小的點3，并標記它為白點。這時的dis[3]=1，然而1卻不是從起點到點3的最短路徑。因為3已被標記為白點，最短路徑值dis[3]不會再被修改了，所以我們在邊權(quán)存在負數(shù)的情況下得到了錯誤的答案！12345213-4562【例4-3】、最短路徑問題(Dijkstra)題目參見“Floyed算法”，但本題要求使用dijkstra算法解決。#include<iostream>#include<cstdio>#include<cstring>#include<cmath>usingnamespacestd;inta[101][3];doublec[101];boolb[101];doublef[101][101];intn,i,j,k,x,y,m,s,e;doubleminl;doublemaxx=1e30;intmain(){cin>>n;for(i=1;i<=n;i++)cin>>a[i][1]>>a[i][2];for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=maxx;//f數(shù)組初始化最大值

cin>>m;for(i=1;i<=m;i++)//預(yù)處理x.y間距離f[x][y]{cin>>x>>y;f[x][y]=f[y][x]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));}

cin>>s>>e;for(i=1;i<=n;i++)c[i]=f[s][i];memset(b,false,sizeof(b)); //dijkstra最短路

b[s]=true;c[s]=0;for(i=1;i<=n-1;i++){minl=maxx;k=0;for(j=1;j<=n;j++)//查找可以更新的點

if((!b[j])&&(c[j]<minl)){minl=c[j];k=j;}if(k==0)break;b[k]=true;for(j=1;j<=n;j++)

if(c[k]+f[k][j]<c[j])c[j]=c[k]+f[k][j];}printf("%.2lf\n",c[e]);return0;}【例4-4】最小花費【問題描述】

在n個人中，某些人的銀行賬號之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費各不相同。給定這些人之間轉(zhuǎn)賬時需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費，請問A最少需要多少錢使得轉(zhuǎn)賬后B收到100元。【輸入格式】

第一行輸入兩個正整數(shù)n,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對數(shù)。以下m行每行輸入三個正整數(shù)x,y,z，表示標號為x的人和標號為y的人之間互相轉(zhuǎn)賬需要扣除z%的手續(xù)費(z<100)。最后一行輸入兩個正整數(shù)A,B。數(shù)據(jù)保證A與B之間可以直接或間接地轉(zhuǎn)賬。【輸出格式】

輸出A使得B到賬100元最少需要的總費用。精確到小數(shù)點后8位?！据斎霕永?312123213313【輸出樣例】103.07153164【數(shù)據(jù)規(guī)模】1<=n<=2000【參考程序】#include<iostream>usingnamespacestd;doublea[2001][2001],dis[2001]={0},minn;intn,m,i,j,k,x,y,f[2001]={0};voidinit(){cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d",&j,&k);scanf("%lf",&a[j][k]);a[j][k]=(100-a[j][k])/100;a[k][j]=a[j][k];}cin>>x>>y;}voiddijkstra(intx){for(i=1;i<=n;i++)dis[i]=a[x][i];dis[x]=1;f[x]=1;for(i=1;i<=n-1;i++){minn=0;for(j=1;j<=n;j++)if(f[j]==0&&dis[j]>minn){k=j;minn=dis[j];}f[k]=1;if(k==y)break;for(j=1;j<=n;j++)if(f[j]==0&&dis[k]*a[k][j]>dis[j])dis[j]=dis[k]*a[k][j];}}intmain(){init();dijkstra(x);printf("%0.8f",100/dis[y]);return0;}3.Bellman-Ford算法O(NE)簡稱Ford（福特）算法，同樣是用來計算從一個點到其他所有點的最短路徑的算法，也是一種單源最短路徑算法。能夠處理存在負邊權(quán)的情況，但無法處理存在負權(quán)回路的情況（下文會有詳細說明）。算法時間復(fù)雜度：O(NE)，N是頂點數(shù)，E是邊數(shù)。算法實現(xiàn)：設(shè)s為起點，dis[v]即為s到v的最短距離，pre[v]為v前驅(qū)。w[j]是邊j的長度，且j連接u、v。初始化：dis[s]=0,dis[v]=∞（v≠s），pre[s]=0For(i=1;i<=n-1;i++)For(j=1;j<=E;j++)

//注意要枚舉所有邊，不能枚舉點。

if(dis[u]+w[j]<dis[v])

//u、v分別是這條邊連接的兩個點。

{dis[v]

=dis[u]

+

w[j];pre[v]

=

u;}算法分析&思想講解：Bellman-Ford算法的思想很簡單。一開始認為起點是白點(dis[1]=0)，每一次都枚舉所有的邊，必然會有一些邊，連接著白點和藍點。因此每次都能用所有的白點去修改所有的藍點，每次循環(huán)也必然會有至少一個藍點變成白點。在上面這個簡單的模擬中能看到白點的“蔓延”情況。負權(quán)回路：雖然Bellman-Ford算法可以求出存在負邊權(quán)情況下的最短路徑，卻無法解決存在負權(quán)回路的情況。

負權(quán)回路是指邊權(quán)之和為負數(shù)的一條回路，上圖中②-④-⑤-③-②這條回路的邊權(quán)之和為-3。在有負權(quán)回路的情況下，從1到6的最短路徑是多少？答案是無窮小，因為我們可以繞這條負權(quán)回路走無數(shù)圈，每走一圈路徑值就減去3，最終達到無窮小。所以說存在負權(quán)回路的圖無法求出最短路徑，Bellman-Ford算法可以在有負權(quán)回路的情況下輸出錯誤提示。如果在Bellman-Ford算法的兩重循環(huán)完成后，還是存在某條邊使得：dis[u]+w<dis[v]，則存在負權(quán)回路：For每條邊(u,v)If(dis[u]+w<dis[v])

returnFalse如果我們規(guī)定每條邊只能走一次，在這個前提下可以求出負權(quán)回路的最短路徑。這個問題就留待讀者自己思考（提示：對Floyed做一點小處理）?！纠?-5】、最短路徑問題(Bellman-Ford)題目參見“Floyed算法”，要求采用Bellman-Ford算法。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;intmain(){doublea[101][3],dis[1001],w[1001],min1;intn,m,x,y,k,f[1001][3],s,t;boolb[101];cin>>n;

for(inti=1;i<=n;i++)

scanf("%lf%lf",&a[i][1],&a[i][2]);cin>>m;for(inti=1;i<=m;i++)

//初始化數(shù)組dis，f{

dis[i]=0x7fffffff;

f[i][1]=f[i][2]=0x7fffffff;}for(inti=1;i<=m;i++){scanf("%d%d",&x,&y);f[i][1]=x;f[i][2]=y;w[i]=sqrt(pow(a[x][1]-a[y][1],2)+pow(a[x][2]-a[y][2],2));}cin>>s>>t;dis[s]=0;for(inti=1;i<=n;i++)//算法主體

for(intj=1;j<=m;j++)

{if(dis[f[j][1]]+w[j]<dis[f[j][2]])dis[f[j][2]]=dis[f[j][1]]+w[j];if(dis[f[j][2]]+w[j]<dis[f[j][1]])dis[f[j][1]]=dis[f[j][2]]+w[j];

}printf("%.2f",dis[t]);}4、SPFA算法O(kE)SPFA是Bellman-Ford算法的一種隊列實現(xiàn)，減少了不必要的冗余計算。主要思想是：初始時將起點加入隊列。每次從隊列中取出一個元素，并對所有與它相鄰的點進行修改，若某個相鄰的點修改成功，則將其入隊。直到隊列為空時算法結(jié)束。這個算法，簡單的說就是隊列優(yōu)化的bellman-ford，利用了每個點不會更新次數(shù)太多的特點發(fā)明的此算法。SPFA在形式上和廣度優(yōu)先搜索非常類似，不同的是廣度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是說一個點修改過其它的點之后，過了一段時間可能會獲得更短的路徑，于是再次用來修改其它的點，這樣反復(fù)進行下去。算法時間復(fù)雜度：O(kE)，E是邊數(shù)。K是常數(shù)，平均值為2。算法實現(xiàn)：dis[i]記錄從起點s到i的最短路徑，w[i][j]記錄連接i，j的邊的長度。pre[v]記錄前趨。team[1..n]為隊列，頭指針head，尾指針tail。

布爾數(shù)組exist[1..n]記錄一個點是否現(xiàn)在存在在隊列中。

初始化：dis[s]=0,dis[v]=∞（v≠s），memset(exist,false,sizeof(exist));

起點入隊team[1]=s;head=0;tail=1;exist[s]=true;

do{

1、頭指針向下移一位，取出指向的點u。2、exist[u]=false;已被取出了隊列3、for與u相連的所有點v

//注意不要去枚舉所有點，用數(shù)組模擬鄰接表存儲

if(dis[v]>dis[u]+w[u][v])

{dis[v]=dis[u]+w[u][v];pre[v]=u;

if(!exist[v])//隊列中不存在v點，v入隊。

{//尾指針下移一位，v入隊;

exist[v]=true;

}｝}while(head<tail);循環(huán)隊列：采用循環(huán)隊列能夠降低隊列大小，隊列長度只需開到2*n+5即可。例題中的參考程序使用了循環(huán)隊列。【例4-6】、香甜的黃油(SweetButter)【問題描述】農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道N（1<=N<=500）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。

農(nóng)夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。農(nóng)夫John知道每只奶牛都在各自喜歡的牧場（一個牧場不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路線，找出使所有牛到達的路程和最短的牧場（他將把糖放在那）。

【輸入格式】butter.in第一行:三個數(shù)：奶牛數(shù)N，牧場數(shù)P（2<=P<=800），牧場間道路數(shù)C(1<=C<=1450)。第二行到第N+1行:1到N頭奶牛所在的牧場號。第N+2行到第N+C+1行：每行有三個數(shù)：相連的牧場A、B，兩牧場間距（1<=D<=255），當然，連接是雙向的。【輸出格式】butter.out一行

輸出奶牛必須行走的最小的距離和.【輸入樣例】345234121135237243345樣例圖形

P2P1@--1--@C1\|\\|\573\|\\|\C3C2@--5--@P3P4【輸出樣例】8//說明：放在4號牧場最優(yōu)【參考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intn,p,c,i,j,x,y,t,min1,head,tail,tot,u;inta[801][801],b[501],dis[801],w[801][801],team[1601];boolexist[801];intmain(){freopen("butter.in","r",stdin);freopen("butter.out","w",stdout);cin>>n>>p>>c;for(i=1;i<=p;i++){

b[i]=0;

a[i][0]=0;for(j=1;j<=p;j++)w[i][j]=0x7fffffff;}for(i=1;i<=n;i++)cin>>b[i];for(i=1;i<=c;i++)//鄰接矩陣存儲

{cin>>x>>y>>t;w[x][y]=t;a[x][++a[x][0]]=y;a[y][++a[y][0]]=x;w[y][x]=w[x][y];}min1=0x7fffffff;for(i=1;i<=p;i++){for(j=1;j<=p;j++)dis[j]=0x7fffffff;memset(team,0,sizeof(team));//隊列數(shù)組初始化memset(exist,false,sizeof(exist));//exist標志初始化dis[i]=0;team[1]=i;head=0;tail=1;exist[i]=true;//起始點入隊do{head++;head=((head-1)%1601)+1;//循環(huán)隊列處理u=team[head];exist[u]=false;for(j=1;j<=a[u][0];j++)if(dis[a[u][j]]>dis[u]+w[u][a[u][j]]){dis[a[u][j]]=dis[u]+w[u][a[u][j]];if(!exist[a[u][j]]){tail++;tail=((tail-1)%1601)+1;team[tail]=a[u][j];exist[a[u][j]]=true;}}}while(head!=tail);tot=0;for(j=1;j<=n;j++)

tot+=dis[b[j]];if(tot<min1)min1=tot;}cout<<min1;return0;}二、輸出最短路徑1.單源最短路徑的輸出Dijkstra，Bellman-Ford，SPFA都是單源最短路徑算法，它們的共同點是都有一個數(shù)組pre[x]用來記錄從起點到x的最短路徑中，x的前驅(qū)結(jié)點是哪個。每次更新，我們就給pre[x]賦一個新值，結(jié)合上面的思想講解，相信對于記錄某點的前驅(qū)結(jié)點是不難理解的。那么怎么利用pre[x]數(shù)組輸出最短路徑方案呢？【例4-7】、最短路徑問題(輸出路徑)要求改寫程序，用Dijkstra、Bellman-Ford、SPFA算法輸出最短路徑的方案。使用一個小小的遞歸過程就能解決這一問題。voidprint(intx){if(pre[a][x]==0)return;//起點的前驅(qū)我們已設(shè)為0print(pre[a][x]);

cout<<"->"<<x;}//主程序中：main{……（進行Dijkstra或Bellman-Ford，SPFA運算）cout<<s;print(e);//s是起點，e是終點}2.Floyed算法輸出最短路徑Floyed算法輸出路徑也是采用記錄前驅(qū)點的方式。因為floyed是計算任意兩點間最短路徑的算法，dis[i][j]記錄從i到j(luò)的最短路徑值。故而我們定義pre[i][j]為一個二維數(shù)組，記錄從i到j(luò)的最短路徑中，j的前驅(qū)點是哪一個。【例4-8】、最短路徑問題(Floyed法輸出路徑)要求改寫Floyed的程序，模仿Dijkstra輸出路徑的方法用floyed輸出最短路徑方案。【參考程序】#include<iostream>#include<cmath>#include<cstring>usingnamespacestd;doubledis[101][101];intx[101],y[101];intpre[101][101];intn,i,j,k,m,a,b;intpf(intx){returnx*x;}voidprint(intx){if(pre[a][x]==0)return;//pre[a][a]=0,說明已經(jīng)遞歸到起點aprint(pre[a][x]);cout<<"->"<<x;}intmain(){cin>>n;for(i=1;i<=n;i++)cin>>x[i]>>y[i];memset(dis,0x7f,sizeof(dis));

//初始化數(shù)組cin>>m;memset(pre,0,sizeof(pre));//初始化前驅(qū)數(shù)組for(i=1;i<=m;i++){cin>>a>>b;dis[a][b]=dis[b][a]=sqrt(pf(x[a]-x[b])+pf(y[a]-y[b]));pre[a][b]=a;

//a與b相連，自然從a到b的最短路徑b的前驅(qū)是apre[b][a]=b;}cin>>a>>b;for(k=1;k<=n;k++)//floyed最短路for