徹底弄懂最短路徑

徹底弄懂最短路徑只想說：溫故而知新，可以為師矣。我大二的《數(shù)據(jù)結(jié)構(gòu)》是由申老師講的，那時候不怎么明白，估計(jì)太理論化了（ps：或許是因?yàn)槲宜X了）；今天把老王的2011年課件又看了一遍，給大二的孩子們又講了一遍，隨手谷歌了N多資料，算是徹底搞懂了最短路徑問題。請讀者盡情享用……我堅(jiān)信：沒有不好的學(xué)生，只有垃圾的教育。不過沒有人理所當(dāng)然的對你好，所以要學(xué)會感恩。一一.問題引入問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑。解決最短路的問題有以下算法，Dijkstra算法，Bellman-Ford算法，F(xiàn)loyd算法和SPFA算法，另外還有著名的啟發(fā)式搜索算法A*，不過A*準(zhǔn)備單獨(dú)出一篇，其中Floyd算法可以求解任意兩點(diǎn)間的最短路徑的長度。筆者認(rèn)為任意一個最短路算法都是基于這樣一個事實(shí)：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個節(jié)點(diǎn)到B。二.Dijkstra算法該算法在《數(shù)據(jù)結(jié)構(gòu)》課本里是以貪心的形式講解的，不過在《運(yùn)籌學(xué)》教材里被編排在動態(tài)規(guī)劃章節(jié)，建議讀者兩篇都看看。300328563176最短路徑蕓度300328563176最短路徑蕓度<VO?V1>13<V0.V2>8<V0:V23V3>1319<V0?V2?V3:V4?V5>21<V0tVLV6>20觀察右邊表格發(fā)現(xiàn)除最后一個節(jié)點(diǎn)外其他均已經(jīng)求出最短路徑。⑴ 迪杰斯特拉(Dijkstra)算法按路徑長度(看下面表格的最后一行，就是next點(diǎn)）遞增次序產(chǎn)生最短路徑。先把V分成兩組:S:已求出最短路徑的頂點(diǎn)的集合V-S=T：S:已求出最短路徑的頂點(diǎn)的集合V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和（反證法可證，說實(shí)話，真不明白哦）。⑵求最短路徑步驟初使時令S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對應(yīng)的距離值，若存在＜V0,Vi＞，為＜V0,Vi〉弧上的權(quán)值（和SPFA初始化方式不同），若不存在＜V0,Vi＞，為Inf。從T中選取一個其距離值為最小的頂點(diǎn)W（貪心體現(xiàn)在此處），加入S（注意不是直接從S集合中選取，理解這個對于理解vis數(shù)組的作用至關(guān)重要），對T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，

則修改此距離值（上面兩個并列for循環(huán)，使用最小點(diǎn)更新）。3.重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止（說明最外層是除起點(diǎn)外的遍歷）。下面是上圖的求解過程，按列來看，第一列是初始化過程，最后一行是每次求得的next點(diǎn)。從￥0從￥0到嚥點(diǎn)的最短路徑及其K度VJ13V0.VI13\0S\\2\0A'2?■BSTrS^ir■HHMRiiiifclih■■■V313V0,V25V|13\QVNV3a￥斗30\0.V430V0.X41S>X0A2A3.V4暑:22AUV1.V522<V0fVUV5>21<V0,vi'V3.V4V5>V632\0\Y)<V0,V6>205\丄丫620<VT0ArLV6>20M.YLY6vjA2:8\0.\2<VO,V1>V313\U\2.\3V4:19\0.V2.\3.V4\620（3）問題：Dijksta能否處理負(fù)權(quán)邊？下面的解釋引自網(wǎng)上某大蝦）答案是不能，這與貪心選擇性質(zhì)有關(guān)（PS貌似還是動態(tài)規(guī)劃啊，暈了）,每次都找一個距源點(diǎn)最近的點(diǎn)（dmin），然后將該距離定為這個點(diǎn)到源點(diǎn)的最短路徑；但如果存在負(fù)權(quán)邊，那就有可能先通過并不是距源點(diǎn)最近的一個次優(yōu)點(diǎn)(dmin')，再通過這個負(fù)權(quán)邊L(L<0)，使得路徑之和更小(dmin'+L<dmin)，則dmin'+L成為最短路徑，并不是dmin，這樣dijkstra就被囧掉了。比如n=3，鄰接矩陣：0,3,43，0，-24，-2，0，用dijkstra求得d[1，2]=3，事實(shí)上d[1，2]=2，就是通過了1-3-2使得路徑減小。不知道講得清楚不清楚。二.Floyd算法參考了南陽理工牛帥(目前在新浪)的博客。Floyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，是直接從A到B,是從A經(jīng)過若干個節(jié)點(diǎn)到B,所以，我們假設(shè)dist(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對于每一個節(jié)點(diǎn)K,我們檢查dist(AK)+dist(KB)<dist(AB)是否成立，如果成立，證明從A到K再到B的路徑比A直接到B的路徑短，我們便設(shè)置dist(AB)=dist(AK)+dist(KB)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)K，dist(AB)中記錄的便是A到B的最短路徑的距離。很簡單吧，代碼看起來可能像下面這樣：for(inti=0;i<n;++i){for(intj=0;j<n;++j){for(intk=0;k<n;++k){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}但是這里我們要注意循環(huán)的嵌套順序，如果把檢查所有節(jié)點(diǎn)K放在最內(nèi)層，那么結(jié)果將是不正確的，為什么呢？因?yàn)檫@樣便過早的把i到j(luò)的最短路徑確定下來了，而當(dāng)后面存在更短的路徑時，已經(jīng)不再會更新了。讓我們來看一個例子，看下圖:圖中紅色的數(shù)字代表邊的權(quán)重。如果我們在最內(nèi)層檢查所有節(jié)點(diǎn)K,那么對于A-〉B，我們只能發(fā)現(xiàn)一條路徑，就是A-〉B，路徑距離為9，而這顯然是不正確的，真實(shí)的最短路徑是A-〉D-〉C-〉B，路徑距離為6。造成錯誤的原因就是我們把檢查所有節(jié)點(diǎn)K放在最內(nèi)層，造成過早的把A到B的最短路徑確定下來了，當(dāng)確定A->B的最短路徑時dist(AC)尚未被計(jì)算。所以，我們需要改寫循環(huán)順序，如下：ps：個人覺得，這和銀行家算法判斷安全狀態(tài)(每種資源去測試所有線程)，樹狀數(shù)組更新(更新所有相關(guān)項(xiàng))一樣的思想。for(intk=0;k<n;++k){

for(inti=0;i<n;++i){for(intj=0;j<n;++j){/*實(shí)際中為防止溢出，往往需要選判斷dist[i][k]和dist[k][j都不是Inf，只要一個是Inf,那么就肯定不必更新。*/if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}如果還是看不懂，那就用草稿紙模擬一遍，之后你就會豁然開朗。半個小時足矣(早知道的話會節(jié)省很多個半小時了。矣(早知道的話會節(jié)省很多個半小時了。再來看路徑保存問題:voidfloyd(){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(map[i][j]==Inf){path[i][j]=-1//表示i->j不通}else{path[i][j]=i//表示i->j前驅(qū)為i}}}for(intk=1;k<=n;k++){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(!(dist[i][k]==Inf||dist[k][j]==Inf)&&dist[i][j]>dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][k]=i;path[i][j]=path[k][j];}}}}}voidprintPath(intfrom,intto){/**這是倒序輸出，若想正序可放入棧中，然后輸出。**這樣的輸出為什么正確呢？個人認(rèn)為用到了最優(yōu)子結(jié)構(gòu)性質(zhì)，*即最短路徑的子路徑仍然是最短路徑*/while(path[from][to]!=from){System.out.print(path[from][to]+"");to=path[from][to];}}《數(shù)據(jù)結(jié)構(gòu)》課本上的那種方式我現(xiàn)在還是不想看，看著不舒服……Floyd算法另一種理解DP，為理論愛好者準(zhǔn)備的，上面這個形式的算法其實(shí)是Floyd算法的精簡版，而真正的Floyd算法是一種基于DP(DynamicProgramming)的最短路徑算法。設(shè)圖G中n個頂點(diǎn)的編號為1到n。令c[i,j,k]表示從i到j(luò)的最短路徑的長度，其中k表示該路徑中的最大頂點(diǎn)，也就是說c[i,j,k]這條最短路徑所通過的中間頂點(diǎn)最大不超過k。因此，如果G中包含邊＜i,j＞，則c[i,j,0]二邊＜i,j＞的長度；若i=j,則c[i,j,O]=O;如果G中不包含邊<i,j>,則c(i,j,0)=+x。c[i,j,n]則是從i到j(luò)的最短路徑的長度。對于任意的k>0,通過分析可以得到：中間頂點(diǎn)不超過k的i至uj的最短路徑有兩種可能：該路徑含或不含中間頂點(diǎn)k。若不含，則該路徑長度應(yīng)為c[i,j,k-1],否則長度為c[i,k,k-1]+c[k,j,k-1]oc[i,j,k]可取兩者中的最小值。狀態(tài)轉(zhuǎn)移方程：c[i,j,k]=min{c[i,j,k-1],c[i,k,k-1]+c[k,j,k-1]},k>0o這樣，問題便具有了最優(yōu)子結(jié)構(gòu)性質(zhì)，可以用動態(tài)規(guī)劃方法來求解?？戳硪粋€DP(直接引用王老師課件)Ani]U]=arcS[i]|j]; 加礙為圖的鄰接矩陣A叫何也gA㈣[訓(xùn)町+A㈣閃[j]}芬中B12…m說了這么多，相信讀者已經(jīng)躍躍欲試了，咱們看一道例題，以ZOJ1092為例：給你一組國家和國家間的部分貨幣匯率兌換表，問你是否存在一種方式，從一種貨幣出發(fā)，經(jīng)過一系列的貨幣兌換，最后返回該貨幣時大于出發(fā)時的數(shù)值（ps:這就是所謂的投機(jī)倒把吧），下面是一組輸入。3 //國家數(shù)USDollar//國家名BritishPoundFrenchFranc3 //貨幣兌換數(shù)USDollar0.5BritishPound//部分貨幣匯率兌換表BritishPound10.0FrenchFrancFrenchFranc0.21USDollar月賽做的題，不過當(dāng)時用的思路是求強(qiáng)連通分量（ps:明明說的，那時我和華杰感覺好有道理），也沒做出來，現(xiàn)在知道了直接floyd算法就ok了。思路分析：輸入的時候可以采用Map<String,Integer〉map=newHashMap<String，Integer〉（）主要是為了獲得再次包含匯率輸入時候的下標(biāo)以建圖（感覺自己寫的好拗口），或者第一次直接存入String數(shù)組str，再次輸入的時候每次遍歷str數(shù)組，若是equals那么就把str的下標(biāo)賦值給該幣種建圖。下面就是floyd算法啦，初始化其它點(diǎn)為-1,對角線為1,采用乘法更新求最大值。三.Bellman-Ford算法為了能夠求解邊上帶有負(fù)值的單源最短路徑問題，Bellman（貝爾曼，動態(tài)規(guī)劃提出者）和Ford（福特）提出了從源點(diǎn)逐次繞過其他頂點(diǎn)，以縮短到達(dá)終點(diǎn)的最短路徑長度的方法。Bellman-ford算法是求含負(fù)權(quán)圖的單源最短路徑算法，效率很低，但代碼很容易寫。即進(jìn)行不停地松弛，每次松弛把每條邊都更新一下，若n-1次松弛后還能更新，則說明圖中有負(fù)環(huán)，無法得出結(jié)果，否則就成功完成。Bellman-ford算法有一個小優(yōu)化：每次松弛先設(shè)一個flag,初值為FALSE，若有邊更新則賦值為TRUE，最終如果還是FALSE則直接成功退出。Bellman-ford算法浪費(fèi)了許多時間做無必要的松弛，所以SPFA算法用隊(duì)列進(jìn)行了優(yōu)化，效果十分顯著，高效難以想象。SPFA還有SLF，LLL，滾動數(shù)組等優(yōu)化。關(guān)于SPFA，請看我這一篇blogs.eom/hxsyl/p/3248391.html遞推公式（求頂點(diǎn)u到源點(diǎn)v的最短路徑）:dist1[u]=Edge[v][u]distk[u]=min{distk-1[u],min{distk-1[j]+Edge[j][u]}},j=0丄…,n-1,jHuDijkstra算法和Bellman算法思想有很大的區(qū)別：Dijkstra算法在求解過程中，源點(diǎn)到集合S內(nèi)各頂點(diǎn)的最短路徑一旦求出，則之后不變了，修改的僅僅是源點(diǎn)到T集合中各頂點(diǎn)的最短路徑長度oBellman算法在求解過程中，每次循環(huán)都要修改所有頂點(diǎn)的dist[]，也就是說源點(diǎn)到各頂點(diǎn)最短路徑長度一直要到Bellman算法結(jié)束才確定下來。算法適用條件.1?單源最短路徑（從源點(diǎn)s到其它所有頂點(diǎn)v）?有向圖&無向圖（無向圖可以看作（u,v），（v,u）同屬于邊集E的有向圖）?邊權(quán)可正可負(fù)（如有負(fù)權(quán)回路輸出錯誤提示）?差分約束系統(tǒng)（至今貌似只看過一道題）Bellman-Ford算法描述:初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值d[v]<—~oo,d[s]迭代求解：反復(fù)對邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次，看下面的描述性證明（當(dāng)做樹））檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false,表明問題無解；否則算法返回true,并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在d[v]中描述性證明：（這個解釋很好）首先指出，圖的任意一條最短路徑既不能包含負(fù)權(quán)回路，也不會包含正權(quán)回路，因此它最多包含|v|-1條邊。其次，從源點(diǎn)s可達(dá)的所有頂點(diǎn)如果存在最短路徑，則這些最短路徑構(gòu)成一個以s為根的最短路徑樹。Bellman-Ford算法的迭代松弛操作，實(shí)際上就是按頂點(diǎn)距離s的層次，逐層生成這棵最短路徑樹的過程。在對每條邊進(jìn)行1遍松弛的時候，生成了從s出發(fā)，層次至多為1的那些樹枝。也就是說，找到了與s至多有1條邊相聯(lián)的那些頂點(diǎn)的最短路徑；對每條邊進(jìn)行第2遍松弛的時候，生成了第2層次的樹枝，就是說找到了經(jīng)過2條邊相連的那些頂點(diǎn)的最短路徑 。因?yàn)樽疃搪窂阶疃嘀话瑋v|-1條邊，所以，只需要循環(huán)|v|-1次。每實(shí)施一次松弛操作，最短路徑樹上就會有一層頂點(diǎn)達(dá)到其最短距離，此后這層頂點(diǎn)的最短距離值就會一直保持不變，不再受后續(xù)松弛操作的影響。（但是，每次還要判斷松弛，這里浪費(fèi)了大量的時間，這就是Bellman-Ford算法效率底下的原因，也正是SPFA優(yōu)化的所在）。不更新，那么點(diǎn)D的最短路徑肯定也無法更新，這就是優(yōu)化所在。如果沒有負(fù)權(quán)回路，由于最短路徑樹的高度最多只能是|v|-1，所以最多經(jīng)過|v|-1遍松弛操作后，所有從s可達(dá)的頂點(diǎn)必將求出最短距離。如果d[v]仍保持+x,則表明從s到V不可達(dá)。如果有負(fù)權(quán)回路，那么第|v|-1遍松弛操作仍然會成功，這時，負(fù)權(quán)回路上的頂點(diǎn)不會收斂。參考來源：.en/s/blog_680342610101411v.html問題：Bellman-Ford算法是否一定要循環(huán)n-1次么？未必！其實(shí)只要在某次循環(huán)過程中，考慮每條邊后，都沒能改變當(dāng)前源點(diǎn)到所有頂點(diǎn)的最短路徑長度，那么Bellman-Ford算法就可以提前結(jié)束了（開篇提出的小優(yōu)化就是這個）。上代碼（來自牛帥）#include<iostream>#include<cstdio>usingnamespacestd;#defineMAX0x3f3f3f3f#defineN1010intnodenum,edgenum,original;//點(diǎn)，邊，起點(diǎn)typedefstruetEdge//邊{intu,v;intcost;}Edge;Edgeedge[N];intdis[N],pre[N];boolBellman_Ford（）{for(inti=1;i<=nodenum;++i)//初始化dis[i]=(i==original?0:MAX);for(inti=1;i<=nodenum-1;++i)for(intj=1;j<=edgenum;++j)if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)//松弛(順序一定不能反~){dis[edge[j]?v]=dis[edge[j]?u]+edge[j]?cost;pre[edge[j].v]=edge[j].u;}boolflag=