單源最短路問題(SSSP問題)單源最短路問題指的是該頂點至所有可達頂點的最短路徑問題.約定：從start到點i的距離為d[i]。如果d[i]==INF,說明start和i不連通。Dijkstra算法！[鄰接矩陣]Dijkstra算法是貪心算法。它只適用于所有邊的權都大于0的圖。它的主要特點是以起始點為中心向外層層擴展(廣度優(yōu)先搜索思想)，直到擴展到終點為止?；舅枷胪ㄟ^Dijkstra計算圖G中的最短路徑時，需要指定起點s(即從頂點s開始計算).此外，引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(以及相應的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)。操作步驟初始時，S只包含起點s；U包含除s外的其他頂點，且U中頂點的距離為"起點s到該頂點的距離”[如，U中頂點v的距離為(s,v)的長度，然后s和v不相鄰，則v的距離為8]。從U中選出"距離最短的頂點k"，并將頂點k加入到S中；同時，從U中移除頂點k。更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k來更新其它頂點的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。重復步驟(2)和(3)，直到遍歷完所有頂點。代碼：時間復雜度：O(n2)boolvisited[N];//是否被標號intd[N];//從起點到某點的最短路徑長度intprev[N];//通過追蹤prev可以得到具體的最短路徑(注意這里是逆序的)voidDijkstra(intstart){//初始化：d[start]=0，且所有點都未被標號memset(visited,0,sizeof(visited));for(inti=0;i<n;i++)d[i]=INF;d[start]=0;//計算n次for(inti=0;i<n;i++){intx,min=INF;//在所有未標號的結點中，選擇一個d值最小的點X。for(inta=0;a<n;a++)if(!visited[a]&&d[a]<min)min=d[x=a];visited[x]=true;//標記這個點x。//對于從x出發(fā)的所有邊(X，y)，更新一下d[y]。for(inty=0;y<n;y++)if(d[y]>d[x]+G[x][y]){d[y]=d[x]+G[x][y];prev[y]=x;//y這個最短路徑是從x走到y(tǒng)。}}Iii^1I第1步：Iii^1I選取頂點D卸5"；J】={A（8）,r（8）,c（3）?E（4）,F（8）,g（8）}；I注』\（OI）S,己計定出最短略徑的定點的染合I（02）U爛未計算出）短路徑的定點的集合\（03）C（3）表示頂點C到起點D的最短隨離宏3第2步x透取頂點C；sHD<br,c(3)F——:^A(oo)2B(23)_.E(4hF(9>業(yè)竺k第3步：選取頂點EUMA(j?)2b(23)2F(6XG(12n使用優(yōu)先隊列的Dijkstra算法*樸素的Dijkstra算法在選d值最小的點時要浪費很多時間，所以可以用優(yōu)先隊列(最小堆)來優(yōu)化。時間復雜度：O[(〃+m)logm],最差情況(密集圖)為O(〃2logm)//需要的頭文件：<queue>、<vector>、<utility>typedefpair<int,int>pii;//將終點和最短路徑長度“捆綁”的類型//定義一個優(yōu)先隊列，d值最小的先出列priority_queue<pii,vector<pii>,greater<pii>>q;intd[N],prev[N];voidDijkstra(intstart){for(inti=0;i<n;i++)d[i]=INF;d[start]=0;q.push(make_pair(d[start],start));while(!q.empty()){//在所有未標號的結點中，選擇一個d值最小的點X。piiu=q.top();q.pop();intx=u.second;if(u.first!=d[x])continue;//已經(jīng)計算完for(edge*e=adj[x];e!=NULL;e=e->next){int&v=e->v,&w=e->w;if(d[v]>d[x]+w){d[v]=d[x]+w;//松弛prev[v]=x;q.push(make_pair(d[v],v));}}}}Bellman-Ford算法[邊目錄]Bellman-Ford算法是迭代法，它不停地調(diào)整圖中的頂點值(源點到該點的最短路徑值)，直到?jīng)]有點的值調(diào)整了為止。該算法除了能計算最短路，還可以檢查負環(huán)(一個每條邊的權都小于0的環(huán))。如果圖中有負環(huán)，那么這個圖不存在最短路。boolFord(intstart){//有負環(huán)則返回falsefor(inti=0;i<n;i++)d[i]=INF;//初始化d[start]=0;for(intk=0;k<n-1;k++)//迭代n次for(inti=0;i<m;i++){//檢查每條邊int&x=u[i],&y=v[i];if(d[x]<INF)d[y]=min(d[y],d[x]+w[i]);}//下面的代碼用于檢查負環(huán)一一如果全部松弛之后還能松弛，說明一定有負環(huán)for(inti=0;i<m;i++){//再次檢查每條邊int&x=u[i],&y=v[i];if(d[y]>d[x]+w[i])returnfalse;}returntrue;}Dijkstra算法是處理單源最短路徑的有效算法，但它局限于邊的權值非負的情況，若圖中出現(xiàn)權值為負的邊，Dijkstra算法就會失效，求出的最短路徑就可能是錯的。這時候，就需要使用其他的算法來求解最短路徑，Bellman-Ford算法就是其中最常用的一個。該算法由美國數(shù)學家理查德?貝爾曼(RichardBellman,動態(tài)規(guī)劃的提出者)和小萊斯特?福特(LesterFord)發(fā)明。適用條件&范圍：單源最短路徑(從源點s到其它所有頂點v);有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)；邊權可正可負(如有負權回路輸出錯誤提示)；差分約束系統(tǒng)；BellmanFord算法的流程如下：給定圖G(V,E)(其中V、E分別為圖G的頂點集與邊集)，源點s，數(shù)組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數(shù)組Distant[n]為，Distant[s]為0；以下操作循環(huán)執(zhí)行至多n-1次，n為頂點數(shù)：對于每一條邊e(u,v)，如果Distant[u]+w(u,v)<Distant[v]，則另Distant[v]=Distant[u]+w(u,v)。w(u,v)為邊e(u,v)的權值；若上述操作沒有對Distant進行更新，說明最短路徑已經(jīng)查找完畢，或者部分點不可達，跳出循環(huán)。否則執(zhí)行下次循環(huán)；為了檢測圖中是否存在負環(huán)路，即權值之和小于0的環(huán)路。對于每一條邊e(u,v)，如果存在Distant[u]+w(u,v)<Distant[v]的邊，則圖中存在負環(huán)路，即是說改圖無法求出單源最短路徑。否則數(shù)組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度?？芍?，Bellman-Ford算法尋找單源最短路徑的時間復雜度為O(V*E).首先介紹一下松弛計算。如下圖：www.WuTianQwww.WuTiflnQ松弛計算之前，點B的值是8,但是點A的值加上邊上的權重2,得到5,比點B的值(8)小，所以，點B的值減小為5。這個過程的意義是，找到了一條通向B點更短的路線，且該路線是先經(jīng)過點A，然后通過權重為2的邊，到達點B。當然，如果出現(xiàn)一下情況二則不會修改點B的值，因為3+4>6。Bellman—Ford算法可以大致分為三個部分第一，初始化所有點。每一個點保存一個值，表示從原點到達這個點的距離，將原點的值設為0，其它的點的值設為無窮大(表示不可達)。第二，進行循環(huán)，循環(huán)下標為從1到n—1(n等于圖中點的個數(shù))。在循環(huán)內(nèi)部，遍歷所有的邊，進行松弛計算。第三，遍歷途中所有的邊(edge(u，v))，判斷是否存在這樣情況：d(v)>d(u)+w(u,v)則返回false,表示途中存在從源點可達的權為負的回路。之所以需要第三部分的原因，是因為，如果存在從源點可達的權為負的回路。則應為無法收斂而導致不能求出最短路徑?？紤]如下的圖：經(jīng)過第一次遍歷后，點B的值變?yōu)?,點C的值變?yōu)?,這時，注意權重為一10的邊，這條邊的存在，導致點A的值變?yōu)橐?。(8+—10=—2)第二次遍歷后，點B的值變?yōu)?，點C變?yōu)?，點A變?yōu)橐?。正是因為有一條負邊在回路中，導致每次遍歷后，各個點的值不斷變小。在回過來看一下bellman—ford算法的第三部分，遍歷所有邊，檢查是否存在d(v)>d(u)+w(u,v)。因為第二部分循環(huán)的次數(shù)是定長的，所以如果存在無法收斂的情況，則肯定能夠在第三部分中檢查出來。比如圖三，此時，點A的值為一2,點B的值為5,邊AB的權重為5,5>-2+5.檢查出來這條邊沒有收斂。所以，Bellman—Ford算法可以解決圖中有權為負數(shù)的邊的單源最短路徑問。SPFA!鄰接表]SPFA是使用隊列實現(xiàn)的Bellman-Ford算法。操作步驟如下：①初始隊列和標記數(shù)組。②源點入隊。對隊首點出發(fā)的所有邊進行松弛操作(即更新最小值)。將不在隊列中的尾結點入隊。⑤隊首點更新完其所有的邊后出隊。queue<int>q;boolinqueue[N];//是否在隊歹。中intcnt[N];//檢查負環(huán)時使用：結點進隊次數(shù)。如果超過n說明有負環(huán)。boolSPFA(intstart){//有負環(huán)則返回false//初始隊列和標記數(shù)組for(inti=0;i<n;i++)d[i]=INF;d[start]=0;memset(cnt,0,sizeof(cnt));q.push(start);//源點入隊cnt[start]++;while(!q.empty()){intx=q.front();q.pop();inqueue[x]=false;//對隊首點出發(fā)的所有邊進行松弛操作(即更新最小值)for(edge*e=adj[x];e!=NULL;e=e->next){int&v=e-＞v,&w=e-＞wif(d[v]＞d[x]+w){d[v]=d[x]+w;if(!inqueue[v]){//將不在隊列中的尾結點入隊inqueue[v]=true;q.push(v);if(++cnt[v]＞n)returnfalse；}}}}//有負環(huán)returntrue;}求單源最短路的SPFA算法的全稱是：ShortestPathFasterAlgorithm,是Bellman-Ford算法0(VE)的一個優(yōu)化，期望的時間復雜度O(2E)，E為圖的邊數(shù)，所以SPFA用在稀疏圖上的效果會更加明顯°SPFA對Bellman-Ford算法優(yōu)化的關鍵之處在于意識到：只有那些在前一遍松弛中改變了距離估計值的點，才可能引起他們的鄰接點的距離估計值的改變。很多時候，給定的圖存在負權邊，這時類似Dijkstra算法(0(VW)，在稠密圖上有優(yōu)勢)便沒有了用武之地，而bellman_ford的復雜度又過高，SPFA算法便派上用場了。算法核心思想：理解這個算法，最好先看看Bellman-Ford，因為他是對Bellman-Ford的一個優(yōu)化，SPFA算法采用了一個隊列，優(yōu)化算法，用數(shù)組dict[]記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設立一個先進先出的隊列用來保存待優(yōu)化的結點，優(yōu)化時每次取出隊首結點u，并且用u點當前的最短路徑估計值對離開u點所指向的結點v進行松弛操作，如果v點的最短路徑估計值有所調(diào)整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止。需要注意的是：僅當圖不存在負權回路時，SPFA能正常工作。如果圖存在負權回路，由于負權回路上的頂點無法收斂，總有頂點在入隊和出隊往返，隊列無法為空，這種情況下SPFA無法正常結束。1記錄每個結點進隊次數(shù)，超過|V|次表示有負權2記錄這個結點在路徑中處于的位置，ord[i]，每次更新的時候ord[i]=ord[x]+1，若超過|V|則表示有負圈....下面舉一個實例來說明SFFA算法是怎樣進行的：設有一個有向圖G={V，E}，其中，V={V0,V1,V2,V3,V4}，E={＜V0,V1〉，＜V0,V4〉，＜V1,V2〉，＜V1,V4〉，＜V2,V3〉，＜V3,V4〉，＜V4,V2〉}={2,10,3,7,4,5,6}，見下圖:算法執(zhí)行時各步的Queue隊的值和D數(shù)組的值由下表所示:表一冥田圖$PF.l算法執(zhí)行的步驟及結果初始第一步第二步第四步第五步queueDqueueDqueueDqueueDdueueDQueueDV00VI0V4:0V20T3008V42V22222g85555g8889§001099g9算法執(zhí)行到第五步后，隊Queue空，算法結束。源點V0到V1的最短路徑為2,到V2的最短路徑為5,到V3的最短路徑為9,到V4的最短路徑為9,結果顯然是正確的。0.1每兩點間最短路問題(APSP問題)！此類問題使用Floyd-Warshall算法解決。它是動態(tài)規(guī)劃算法?；舅枷胪ㄟ^Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入一個矩陣S，矩陣S中的元素a[i][j]表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。假設圖G中頂點個數(shù)為N，則需要對矩陣S進行N次更新。初始時，矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權值；如果i和j不相鄰，則a[i][j]=8。接下來開始，對矩陣S進行N次更新。第1次更新時，如果"a[i][j]的距"a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i與j之間經(jīng)過第1個頂點的距離")，則更新a[i][j]為"a[i][0]+a[0][j]"。同理，第k次更新時，如果"a[i][j]的距離">"a[i][k]+a[k][j]”，則更新a[i][j]為"a[i][k]+a[k][j]”。更新N次之后，操作完成！代碼：時間復雜度：O(n3)intf[N][N],prev[N][N];//追蹤prev可以得到最短路。intlen=INF;//最小環(huán)的長度voidFloyd(){for(inti=0;i<n;i++)//初始化可以在讀圖時完成for(intj=0;j<n;j++)f[i][j]=G[i][j];memset(prev,-1,sizeof(prev));/*len=INF;*/for(intk=0;k<n;k++){//計算。注意，k在最外面。/*如果求最小環(huán)，請將下面的代碼插入到這里。大/for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(f[i][k]+f[k][j]<f[i][j]){f[i][j]=f[i][k]+f[k][j];prev[i][j]=k;}}}//cout<<f[i][j]<<endl;//通過遞歸調(diào)用追蹤prev，就可以得到最短路徑上的結點。Floyd算法可以用來求最小環(huán)(無向圖！)。將以下代碼插入到上面的標記處即可。for(inti=0;i<k;i++)for(intj=i+1;j<k;j++)len=min(len,G[i][j]+f[i][k]+f[k][j]);//G是無向圖！len為最小環(huán)的和ABCDEFG012INFINFINF1614*12010INFINF726TNF10356INFIMINF304INFINFINEINF540281676INF2091426INFINF890-466F890123mI1676NF2o9IFF54o28/NNFF3o4FENNNNIIJ14669890123367692094AP12C22D2527F16G14B120101315726C22100636D25133939F2715528167609G1126363990■「433289f1211/fzrLpzr-rr189D2213613716A0122222181614//0.2最小生成樹(MST)已知n個城市，并且已知它們之間的距離。問怎樣修路才能保證道路總長最短，并且每個城市都被連接？(1)Prim算法[鄰接矩陣]Prim算法是貪心算法，貪心策略為：找到目前情況下能連上的權值最小的邊的另一端點，加入之，直到所有的頂點加入完畢。是用來求加權連通圖的最小生成樹的算法。Prim適用于稠密圖。樸素Prim的時間復雜度是O(n2)，因為在尋找離生成樹最近的未加入頂點時浪費了很多時間。所以，可以用堆進行優(yōu)化。堆優(yōu)化后的Prim算法的時間復雜度為O(mlogn)。堆優(yōu)化Prim的代碼比較復雜，并查集優(yōu)化的Kruskal算法與它相比，要好很多。intminEdge[N],cloest[N];//與點N連接的最小邊intPrim(intstart=0){//start的出度不能為0！intans=0,k=0,min;//加入第一個點for(inti=0;i<n;i++){minEdge[i]=G[start][i];cloest[i]=start;}minEdge[start]=0;for(inti=0;i<n-1;i++){min=INF;//尋找離生成樹最近的未加入頂點kfor(intj=0;j<n;j++)if(minEdge[j]!=0&&minEdge[j]<min)min=minEdge[k=j];//把找到的邊加入到MST中ans+=minEdge[k];minEdge[k]=0;//加入完畢。以后不用再處理這個點。//重新計算最短邊f(xié)or(intj=0;j<n;j++)if(G[k][j]<minEdge[j]){minEdge[j]=G[k][j];cloest[j]=k;}}returnans;}基本思想對于圖G而言，V是所有頂點的集合；現(xiàn)在，設置兩個新的集合U和T，其中U用于存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。從所有uCU，vC(V-U)(V-U表示出去U的所有頂點)的邊中選取權值最小的邊(u,v)，將頂點v加入集合U中，將邊(u,▽)加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，這時集合T中包含了最小生成樹中的所有邊。；U^{A}；[Yrt'Z^c,d,e^e,g}_;.OHBOHB4MB4；u=M,?r:KZ色蛀,財I；U=-M.b,14喜9!wnm[V-U={ClD?G}第4步；選取頂點E:UE"hK瓦PE一一］:也二儀七___(2)Kruskal算法！[邊目錄]在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網(wǎng)的最小生成樹。Kruskal算法是貪心算法，貪心策略為：選目前情況下能連上的權值最小的邊，若與以生成的樹不夠成環(huán)，加入之，直到n-1條邊加入完畢。時間復雜度為O(〃logm)，最差情況為O(mlog〃)。相比于Prim，這個算法更常用。intparent[N],rank[M];//p代表并查集，r是邊的序號intcomp(constinti,constintj){returnw[i]<w[j];}//排序時使用intfind(intx){//帶路徑壓縮的查找函數(shù)returnpare