c++編程入門第六次課

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

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

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

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

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

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

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

154321【參考程序】Euler.cpp#include<iostream>#include<cstring>usingnamespacestd;#definemaxn101intg[maxn][maxn];//此圖用鄰接矩陣存儲(chǔ)intdu[maxn];//記錄每個(gè)點(diǎn)的度，就是相連的邊的數(shù)目intcircuit[maxn];//用來記錄找到的歐拉路的路徑intn,e,circuitpos,i,j,x,y,start;voidfind_circuit(inti)//這個(gè)點(diǎn)深度優(yōu)先遍歷過程尋找歐拉路{intj;for(j=1;j<=n;j++)if(g[i][j]==1)//從任意一個(gè)與它相連的點(diǎn)出發(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)計(jì)每個(gè)點(diǎn)的度du[y]++;}start=1;//如果有奇點(diǎn)，就從奇點(diǎn)開始尋找，這樣找到的就是for(i=1;i<=n;i++)//歐拉路。沒有奇點(diǎn)就從任意點(diǎn)開始，if(du[i]%2==1)//這樣找到的就是歐拉回路。(因?yàn)槊恳粋€(gè)點(diǎn)都是偶點(diǎn))start=i;circuitpos=0;find_circuit(start);for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<'';cout<<endl;return0;}注意以上程序具有一定的局限性，對(duì)于下面這種情況它不能很好地處理：上圖具有多個(gè)歐拉回路，而本程序只能找到一個(gè)回路。讀者在遇到具體問題時(shí)，還應(yīng)對(duì)程序作出相應(yīng)的修改。三、哈密爾頓環(huán)歐拉回路是指不重復(fù)地走過所有路徑的回路，而哈密爾頓環(huán)是指不重復(fù)地走過所有的點(diǎn)，并且最后還能回到起點(diǎn)的回路。使用簡單的深度優(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ù)組模擬鄰接表存儲(chǔ)，訪問點(diǎn)i，last表示上次訪問的點(diǎn){visited[i]=true;//標(biāo)記為已經(jīng)訪問過v1[i]=true;//標(biāo)記為已在一張圖中出現(xiàn)過ans[++length]=i;//記錄下答案for(intj=1;j<=num[i];j++){if(g[i][j]==x&&g[i][j]!=last)//回到起點(diǎn)，構(gòu)成哈密爾頓環(huán){ ans[++length]=g[i][j];print();//這里說明找到了一個(gè)環(huán)，則輸出ans數(shù)組。 length--; break; }if(!visited[g[i][j]])dfs(i,g[i][j]);//遍歷與i相關(guān)聯(lián)的所有未訪問過的頂點(diǎn)}length--;visited[i]=false;//這里是回溯過程，注意v1的值不恢復(fù)。}intmain(){memset(visited,false,sizeof(visited));memset(v1,false,sizeof(v1));for(x=1;x<=n;x++)//每一個(gè)點(diǎn)都作為起點(diǎn)嘗試訪問，因?yàn)椴皇菑娜魏我稽c(diǎn)開始都能找過整個(gè)圖的if(!v1[x])//如果點(diǎn)x不在之前曾經(jīng)被訪問過的圖里。{length=0;//定義一個(gè)ans數(shù)組存答案，length記答案的長度。dfs(x);}return0;}第三節(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í)，有些算法不適用。一、求出最短路徑的長度以下沒有特別說明的話，dis[u][v]表示從u到v最短路徑長度，w[u][v]表示連接u，v的邊的長度。1.Floyed-Warshall算法O(N3)簡稱Floyed(弗洛伊德)算法，是最簡單的最短路徑算法，可以計(jì)算圖中任意兩點(diǎn)間的最短路徑。Floyed的時(shí)間復(fù)雜度是O(N3)，適用于出現(xiàn)負(fù)邊權(quán)的情況。算法描述：初始化：點(diǎ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)中間點(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è)更短的路徑長度來更新原先點(diǎn)i到點(diǎn)j的距離。在上圖中，因?yàn)閐is[1][3]+dis[3][2]<dis[1][2]，所以就用dis[1][3]+dis[3][2]來更新原先1到2的距離。我們在初始化時(shí)，把不相連的點(diǎn)之間的距離設(shè)為一個(gè)很大的數(shù)，不妨可以看作這兩點(diǎn)相隔很遠(yuǎn)很遠(yuǎn)，如果兩者之間有最短路徑的話，就會(huì)更新成最短路徑的長度。Floyed算法的時(shí)間復(fù)雜度是O(N3)。123216Floyed算法變形：如果是一個(gè)沒有邊權(quán)的圖，把相連的兩點(diǎn)間的距離設(shè)為dis[i][j]=true，不相連的兩點(diǎn)設(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]);用這個(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)均在-10000~10000之間。其中的一些點(diǎn)之間有連線。若有連線，則表示可從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)，即兩點(diǎn)間有通路，通路的距離為兩點(diǎn)間的直線距離?，F(xiàn)在的任務(wù)是找出從一點(diǎn)到另一點(diǎn)之間的最短路徑?！据斎敫袷健枯斎胛募閟hort.in，共n+m+3行，其中:第一行為整數(shù)n。第2行到第n+1行（共n行），每行兩個(gè)整數(shù)x和y，描述了一個(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)?！据敵龈袷健枯敵鑫募閟hort.out，僅一行，一個(gè)實(shí)數(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ū)稱為一個(gè)牧場。但是就目前而言，你能看到至少有兩個(gè)牧區(qū)不連通?，F(xiàn)在，John想在農(nóng)場里添加一條路徑(注意，恰好一條)。對(duì)這條路徑有這樣的限制：一個(gè)牧場的直徑就是牧場中最遠(yuǎn)的兩個(gè)牧區(qū)的距離(本題中所提到的所有距離指的都是最短的距離)。考慮如下的兩個(gè)牧場，圖１是有5個(gè)牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。每一個(gè)牧區(qū)都有自己的坐標(biāo)：圖１所示的牧場的直徑大約是12.07106,最遠(yuǎn)的兩個(gè)牧區(qū)是A和E，它們之間的最短路徑是A-B-E。這兩個(gè)牧場都在John的農(nóng)場上。John將會(huì)在兩個(gè)牧場中各選一個(gè)牧區(qū)，然后用一條路徑連起來，使得連通后這個(gè)新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同一個(gè)牧區(qū)相交，我們才認(rèn)為它們是連通的?，F(xiàn)在請你編程找出一條連接兩個(gè)不同牧場的路徑，使得連上這條路徑后，這個(gè)更大的新牧場有最小的直徑?！据斎敫袷健康?行：一個(gè)整數(shù)N(1<=N<=150),表示牧區(qū)數(shù)；第2到N+1行：每行兩個(gè)整數(shù)X，Y(0<=X，Y<=100000)，表示N個(gè)牧區(qū)的坐標(biāo)。每個(gè)牧區(qū)的坐標(biāo)都是不一樣的。第N+2行到第2*N+1行：每行包括N個(gè)數(shù)字(0或1)表示一個(gè)對(duì)稱鄰接矩陣。例如，題目描述中的兩個(gè)牧場的矩陣描述如下：ABCDEFGH

A01000000

B10111000

C01001000

D01001000

E01110000

F00000010

G00000101

H00000010

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

8

1010

1510

2010

1515

2015

3015

2510

3010

01000000

10111000

01001000

01001000

01110000

00000010

00000101

00000010【輸出樣例】

22.071068【算法分析】用Floyd求出任兩點(diǎn)間的最短路，然后求出每個(gè)點(diǎn)到所有可達(dá)的點(diǎn)的最大距離，記做mdis[i]。（Floyd算法）r1=max(mdis[i])然后枚舉不連通的兩點(diǎn)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)用來計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，是一種單源最短路徑算法。也就是說，只能計(jì)算起點(diǎn)只有一個(gè)的情況。Dijkstra的時(shí)間復(fù)雜度是O(N2)，它不能處理存在負(fù)邊權(quán)的情況。算法描述：

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

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

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

2.u標(biāo)記為已確定最短路徑

3.For與u相連的每個(gè)未確定最短路徑的頂點(diǎn)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é)點(diǎn)，用來輸出路徑。算法分析&思想講解：從起點(diǎn)到一個(gè)點(diǎn)的最短路徑一定會(huì)經(jīng)過至少一個(gè)“中轉(zhuǎn)點(diǎn)”（例如下圖1到5的最短路徑，中轉(zhuǎn)點(diǎn)是2。特殊地，我們認(rèn)為起點(diǎn)1也是一個(gè)“中轉(zhuǎn)點(diǎn)”）。顯而易見，如果我們想求出起點(diǎn)到一個(gè)點(diǎn)的最短路徑，那我們必然要先求出中轉(zhuǎn)點(diǎn)的最短路徑（例如我們必須先求出點(diǎn)2的最短路徑后，才能求出從起點(diǎn)到5的最短路徑）。中轉(zhuǎn)點(diǎn)終點(diǎn)最短路1101221、2331、2、3441、254

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

=

0，其他的點(diǎn)dis[i]

=

0x7fffffff。123452471162第一輪循環(huán)找到dis[1]最小，將1變成白點(diǎn)。對(duì)所有的藍(lán)點(diǎn)做出修改，使得dis[2]=2,dis[3]=4,dis[4]=7。這時(shí)dis[2]，dis[3]，dis[4]被它的最后一個(gè)中轉(zhuǎn)點(diǎn)1修改為了最短路徑。123452471162第二輪循環(huán)找到dis[2]最小，將2變成白點(diǎn)。對(duì)所有的藍(lán)點(diǎn)做出修改，使得dis[3]=3,dis[5]=4。這時(shí)dis[3]，dis[5]被它們的最后一個(gè)中轉(zhuǎn)點(diǎn)2修改為了最短路徑。123452471162第三輪循環(huán)找到dis[3]最小，將3變成白點(diǎn)。對(duì)所有的藍(lán)點(diǎn)做出修改，使得dis[4]=4。發(fā)現(xiàn)以3為中轉(zhuǎn)不能修改5，說明3不是5的最后一個(gè)中轉(zhuǎn)點(diǎn)。這時(shí)dis[4]也被它的最后一個(gè)中轉(zhuǎn)點(diǎn)3修改為了最短路徑。接下來的兩輪循環(huán)將4、5也變成白點(diǎn)。N輪循環(huán)結(jié)束后，所有的點(diǎn)的最短路徑即能求出。Dijkstra無法處理邊權(quán)為負(fù)的情況，例如右圖這個(gè)例子。2到3的邊權(quán)值為-4，顯然從起點(diǎn)1到3的最短路徑是-2（1→2→3），但是dijskstra在第二輪循環(huán)開始時(shí)會(huì)找到當(dāng)前dis[i]最小的點(diǎn)3，并標(biāo)記它為白點(diǎn)。這時(shí)的dis[3]=1，然而1卻不是從起點(diǎn)到點(diǎn)3的最短路徑。因?yàn)?已被標(biāo)記為白點(diǎn)，最短路徑值dis[3]不會(huì)再被修改了，所以我們在邊權(quán)存在負(fù)數(shù)的情況下得到了錯(cuò)誤的答案！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++)//查找可以更新的點(diǎn)

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】最小花費(fèi)【問題描述】

在n個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請問A最少需要多少錢使得轉(zhuǎn)賬后B收到100元?！据斎敫袷健?/p>

第一行輸入兩個(gè)正整數(shù)n,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。以下m行每行輸入三個(gè)正整數(shù)x,y,z，表示標(biāo)號(hào)為x的人和標(biāo)號(hào)為y的人之間互相轉(zhuǎn)賬需要扣除z%的手續(xù)費(fèi)(z<100)。最后一行輸入兩個(gè)正整數(shù)A,B。數(shù)據(jù)保證A與B之間可以直接或間接地轉(zhuǎn)賬?！据敵龈袷健?/p>

輸出A使得B到賬100元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后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（福特）算法，同樣是用來計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，也是一種單源最短路徑算法。能夠處理存在負(fù)邊權(quán)的情況，但無法處理存在負(fù)權(quán)回路的情況（下文會(huì)有詳細(xì)說明）。算法時(shí)間復(fù)雜度：O(NE)，N是頂點(diǎn)數(shù)，E是邊數(shù)。算法實(shí)現(xiàn)：設(shè)s為起點(diǎn)，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++)

//注意要枚舉所有邊，不能枚舉點(diǎn)。

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

//u、v分別是這條邊連接的兩個(gè)點(diǎn)。

{dis[v]

=dis[u]

+

w[j];pre[v]

=

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

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

returnFalse如果我們規(guī)定每條邊只能走一次，在這個(gè)前提下可以求出負(fù)權(quán)回路的最短路徑。這個(gè)問題就留待讀者自己思考（提示：對(duì)Floyed做一點(diǎn)小處理）?！纠?-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算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。主要思想是：初始時(shí)將起點(diǎn)加入隊(duì)列。每次從隊(duì)列中取出一個(gè)元素，并對(duì)所有與它相鄰的點(diǎn)進(jìn)行修改，若某個(gè)相鄰的點(diǎn)修改成功，則將其入隊(duì)。直到隊(duì)列為空時(shí)算法結(jié)束。這個(gè)算法，簡單的說就是隊(duì)列優(yōu)化的bellman-ford，利用了每個(gè)點(diǎn)不會(huì)更新次數(shù)太多的特點(diǎn)發(fā)明的此算法。SPFA在形式上和廣度優(yōu)先搜索非常類似，不同的是廣度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是說一個(gè)點(diǎn)修改過其它的點(diǎn)之后，過了一段時(shí)間可能會(huì)獲得更短的路徑，于是再次用來修改其它的點(diǎn)，這樣反復(fù)進(jìn)行下去。算法時(shí)間復(fù)雜度：O(kE)，E是邊數(shù)。K是常數(shù)，平均值為2。算法實(shí)現(xiàn)：dis[i]記錄從起點(diǎn)s到i的最短路徑，w[i][j]記錄連接i，j的邊的長度。pre[v]記錄前趨。team[1..n]為隊(duì)列，頭指針head，尾指針tail。

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

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

起點(diǎn)入隊(duì)team[1]=s;head=0;tail=1;exist[s]=true;

do{

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

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

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

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

if(!exist[v])//隊(duì)列中不存在v點(diǎn)，v入隊(duì)。

{//尾指針下移一位，v入隊(duì);

exist[v]=true;

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

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

【輸入格式】butter.in第一行:三個(gè)數(shù)：奶牛數(shù)N，牧場數(shù)P（2<=P<=800），牧場間道路數(shù)C(1<=C<=1450)。第二行到第N+1行:1到N頭奶牛所在的牧場號(hào)。第N+2行到第N+C+1行：每行有三個(gè)數(shù)：相連的牧場A、B，兩牧場間距（1<=D<=255），當(dāng)然，連接是雙向的?！据敵龈袷健縝utter.out一行

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

P2P1@--1--@C1\|\\|\573\|\\|\C3C2@--5--@P3P4【輸出樣例】8//說明：放在4號(hào)牧場最優(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++)//鄰接矩陣存儲(chǔ)

{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));//隊(duì)列數(shù)組初始化memset(exist,false,sizeof(exist));//exist標(biāo)志初始化dis[i]=0;team[1]=i;head=0;tail=1;exist[i]=true;//起始點(diǎn)入隊(duì)do{head++;head=((head-1)%1601)+1;//循環(huán)隊(duì)列處理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都是單源最短路徑算法，它們的共同點(diǎn)是都有一個(gè)數(shù)組pre[x]用來記錄從起點(diǎn)到x的最短路徑中，x的前驅(qū)結(jié)點(diǎn)是哪個(gè)。每次更新，我們就給pre[x]賦一個(gè)新值，結(jié)合上面的思想講解，相信對(duì)于記錄某點(diǎn)的前驅(qū)結(jié)點(diǎn)是不難理解的。那么怎么利用pre[x]數(shù)組輸出最短路徑方案呢？【例4-7】、最短路徑問題(輸出路徑)要求改寫程序，用Dijkstra、Bellman-Ford、SPFA算法輸出最短路徑的方案。使用一個(gè)小小的遞歸過程就能解決這一問題。voidprint(intx){if(pre[a][x]==0)return;//起點(diǎn)的前驅(qū)我們已設(shè)為0print(pre[a][x]);

cout<<"->"<<x;}//主程序中：main{……（進(jìn)行Dijkstra或Bellman-Ford，SPFA運(yùn)算）cout<<s;print(e);//s是起點(diǎn)，e是終點(diǎn)}2.Floyed算法輸出最短路徑Floyed算法輸出路徑也是采用記錄前驅(qū)點(diǎn)的方式。因?yàn)閒loyed是計(jì)算任意兩點(diǎn)間最短路徑的算法，dis[i][j]記錄從i到j(luò)的最短路徑值。故而我們定義pre[i][j]為一個(gè)二維數(shù)組，記錄從i到j(luò)的最短路徑中，j的前驅(qū)點(diǎn)是哪一個(gè)?！纠?-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)遞歸到起點(diǎn)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