徹底弄懂最短路徑問題

1、徹底弄懂最短路徑問題        只想說：溫故而知新，可以為師矣。我大二的數(shù)據(jù)結構是由申老師講的，那時候不怎么明白，估計太理論化了(ps：或許是因為我睡覺了)；今天把老王的2011年課件又看了一遍，給大二的孩子們又講了一遍，隨手谷歌了N多資料，算是徹底搞懂了最短路徑問題。請讀者盡情享用        我堅信：沒有不好的學生，只有垃圾的教育。不過沒有人理所當然的對你好，所以要學會感恩。一.問題引入     

2、   問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑最短路徑。解決最短路的問題有以下算法，Dijkstra算法，Bellman-Ford算法，F(xiàn)loyd算法和SPFA算法，另外還有著名的啟發(fā)式搜索算法A*，不過A*準備單獨出一篇，其中Floyd算法可以求解任意兩點間的最短路徑的長度。筆者認為任意一個最短路算法都是基于這樣一個事實：從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節(jié)點到B。二.Dijkstra算法        該算

3、法在數(shù)據(jù)結構課本里是以貪心的形式講解的，不過在運籌學教材里被編排在動態(tài)規(guī)劃章節(jié)，建議讀者兩篇都看看。                   觀察右邊表格發(fā)現(xiàn)除最后一個節(jié)點外其他均已經求出最短路徑。        (1)   迪杰斯特拉(Dijkstra)算法按路徑長度(看下面表格的最后一行，就是next點)遞增次序產生最短路徑。先

4、把V分成兩組：· S：已求出最短路徑的頂點的集合· V-S=T：尚未確定最短路徑的頂點集合        將T中頂點按最短路徑遞增的次序加入到S中，依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值或是從V0經S中頂點到Vk的路徑權值之和（反證法可證，說實話，真不明白哦）。        (2)   求最短路徑步驟1. 初使時令 S=V0,T=其余頂點，T中頂點對應的距離值， 若存

5、在<V0,Vi>，為<V0,Vi>弧上的權值（和初始化方式不同），若不存在<V0,Vi>，為Inf。2. 從T中選取一個其距離值為最小的頂點W(貪心體現(xiàn)在此處)，加入S(注意不是直接從S集合中選取，理解這個對于理解vis數(shù)組的作用至關重要)，對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值（上面兩個并列for循環(huán)，使用最小點更新）。3. 重復上述步驟，直到S中包含所有頂點，即S=V為止（說明最外層是除起點外的遍歷）。        下面

6、是上圖的求解過程，按列來看，第一列是初始化過程，最后一行是每次求得的next點。                   (3)   問題：Dijkstar能否處理負權邊？（來自圖論）             答案是不能，這與貪心選擇性質有關(ps：貌似還是動態(tài)規(guī)劃啊，暈了)，每次都

7、找一個距源點最近的點（dmin），然后將該距離定為這個點到源點的最短路徑；但如果存在負權邊，那就有可能先通過并不是距源點最近的一個次優(yōu)點（dmin'），再通過這個負權邊L(L<0)，使得路徑之和更?。╠min'+L<dmin）,則dmin'+L成為最短路徑，并不是dmin，這樣dijkstra就被囧掉了。比如n=3，鄰接矩陣： 0，3，4 3，0，-2 4，-2，0,用dijkstra求得d1，2=3，事實上d1，2=2，就是通過了1-3-2使得路徑減小。不知道講得清楚不清楚。二.Floyd算法   

8、;     參考了南陽理工牛帥(目前在新浪)的博客。        Floyd算法的基本思想如下：從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節(jié)點到B，所以，我們假設dist(AB)為節(jié)點A到節(jié)點B的最短路徑的距離，對于每一個節(jié)點K，我們檢查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，證明從A到K再到B的路徑比A直接到B的路徑短，我們便設置 dist(AB) = dist(AK) + dist(KB)，

9、這樣一來，當我們遍歷完所有節(jié)點K，dist(AB)中記錄的便是A到B的最短路徑的距離。        很簡單吧，代碼看起來可能像下面這樣：for (int i=0; i<n; +i) for (int j=0; j<n; +j) for (int k=0; k<n; +k) if (distik + distkj < distij ) distij = distik + distkj;         但是這里我們要注意循環(huán)的嵌套順

10、序，如果把檢查所有節(jié)點K放在最內層，那么結果將是不正確的，為什么呢？因為這樣便過早的把i到j的最短路徑確定下來了，而當后面存在更短的路徑時，已經不再會更新了。        讓我們來看一個例子，看下圖：        圖中紅色的數(shù)字代表邊的權重。如果我們在最內層檢查所有節(jié)點K，那么對于A->B，我們只能發(fā)現(xiàn)一條路徑，就是A->B，路徑距離為9，而這顯然是不正確的，真實的最短路徑是A->D->C->B，路徑距離為6。造成錯誤的原

11、因就是我們把檢查所有節(jié)點K放在最內層，造成過早的把A到B的最短路徑確定下來了，當確定A->B的最短路徑時dist(AC)尚未被計算。所以，我們需要改寫循環(huán)順序，如下：        ps：個人覺得，這和銀行家算法判斷安全狀態(tài)(每種資源去測試所有線程)，樹狀數(shù)組更新(更新所有相關項)一樣的思想。for (int k=0; k<n; +k) for (int i=0; i<n; +i) for (int j=0; j<n; +j) /* 實際中為防止溢出，往往需要選判斷 distik和distkj 都不是

12、Inf ，只要一個是Inf，那么就肯定不必更新。 */ if (distik + distkj < distij ) distij = distik + distkj;         如果還是看不懂，那就用草稿紙模擬一遍，之后你就會豁然開朗。半個小時足矣（早知道的話會節(jié)省很多個半小時了。）       再來看路徑保存問題：void floyd() for(int i=1; i<=n ; i+) for(int j=1; j<= n; j+) if

13、(mapij=Inf) pathij = -1;/表示 i -> j 不通 else pathij = i;/ 表示 i -> j 前驅為 i for(int k=1; k<=n; k+) for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) if(!(distik=Inf|distkj=Inf)&&distij > distik + distkj) distij = distik + distkj; pathik = i; pathij = pathkj; void printPath(int from

14、, int to) /* * 這是倒序輸出，若想正序可放入棧中，然后輸出。 * * 這樣的輸出為什么正確呢？個人認為用到了最優(yōu)子結構性質， * 即最短路徑的子路徑仍然是最短路徑 */ while(pathfromto!=from) System.out.print(pathfromto +""); to = pathfromto;         數(shù)據(jù)結構課本上的那種方式我現(xiàn)在還是不想看，看著不舒服        Floyd算法另一種理

15、解DP，為理論愛好者準備的，上面這個形式的算法其實是Floyd算法的精簡版，而真正的Floyd算法是一種基于DP(Dynamic Programming)的最短路徑算法。設圖G中n 個頂點的編號為1到n。令c i, j, k表示從i 到j 的最短路徑的長度，其中k 表示該路徑中的最大頂點，也就是說ci,j,k這條最短路徑所通過的中間頂點最大不超過k。因此，如果G中包含邊<i, j>，則ci, j, 0 =邊<i, j> 的長度；若i= j ，則ci,j,0=0；如果G中不包含邊<i, j>，則c (i, j, 0)= +。ci, j, n 則是從i 到j 的

16、最短路徑的長度。對于任意的k>0，通過分析可以得到：中間頂點不超過k 的i 到j 的最短路徑有兩種可能：該路徑含或不含中間頂點k。若不含，則該路徑長度應為ci, j, k-1，否則長度為 ci, k, k-1 +c k, j, k-1。ci, j, k可取兩者中的最小值。狀態(tài)轉移方程：ci, j, k=minci, j, k-1, c i, k, k-1+c k, j, k-1，k0。這樣，問題便具有了最優(yōu)子結構性質，可以用動態(tài)規(guī)劃方法來求解。        看另一個DP(直接引用王老師課件)  &

17、#160;                             說了這么多，相信讀者已經躍躍欲試了，咱們看一道例題，以ZOJ 1092為例：給你一組國家和國家間的部分貨幣匯率兌換表，問你是否存在一種方式，從一種貨幣出發(fā)，經過一系列的貨幣兌換，最后返回該貨幣時大于出發(fā)時的數(shù)值(ps：這就是所謂的投機倒把吧)，下面是一

18、組輸入。 3    /國家數(shù) USDollar  /國家名 BritishPound FrenchFranc    3    /貨幣兌換數(shù) USDollar 0.5 BritishPound  /部分貨幣匯率兌換表 BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar        月賽做的

19、題，不過當時用的思路是求強連通分量(ps：明明說的，那時我和華杰感覺好有道理)，也沒做出來，現(xiàn)在知道了直接floyd算法就ok了。        思路分析：輸入的時候可以采用Map<String,Integer> map = new HashMap<String,Integer>()主要是為了獲得再次包含匯率輸入時候的下標以建圖(感覺自己寫的好拗口)，或者第一次直接存入String數(shù)組str，再次輸入的時候每次遍歷str數(shù)組，若是equals那么就把str的下標賦值給該幣種建圖。下面就是floyd算法

20、啦，初始化其它點為-1，對角線為1，采用乘法更新求最大值。三.Bellman-Ford算法        為了能夠求解邊上帶有負值的單源最短路徑問題，Bellman(貝爾曼，動態(tài)規(guī)劃提出者)和Ford(福特)提出了從源點逐次繞過其他頂點，以縮短到達終點的最短路徑長度的方法。 Bellman-ford算法是求含負權圖的單源最短路徑算法，效率很低，但代碼很容易寫。即進行不停地松弛，每次松弛把每條邊都更新一下，若n-1次松弛后還能更新，則說明圖中有負環(huán)，無法得出結果，否則就成功完成。Bellman-ford算法有一個小優(yōu)

21、化：每次松弛先設一個flag，初值為FALSE，若有邊更新則賦值為TRUE，最終如果還是FALSE則直接成功退出。Bellman-ford算法浪費了許多時間做無必要的松弛，所以SPFA算法用隊列進行了優(yōu)化，效果十分顯著，高效難以想象。SPFA還有SLF，LLL，滾動數(shù)組等優(yōu)化。        關于SPFA，請看我這一篇        遞推公式(求頂點u到源點v的最短路徑)：      &

22、#160;  dist 1 u = Edgevu         dist k u = min dist k-1 u, min dist k-1 j + Edgeju , j=0,1,n-1,ju         Dijkstra算法和Bellman算法思想有很大的區(qū)別：Dijkstra算法在求解過程中，源點到集合S內各頂點的最短路徑一旦求出，則之后不變了，修改  的僅僅是源點到T集合中各頂點的最短路徑長度。Bell

23、man算法在求解過程中，每次循環(huán)都要修改所有頂點的dist ，也就是說源點到各頂點最短路徑長度一直要到Bellman算法結束才確定下來。        算法適用條件· 1.單源最短路徑(從源點s到其它所有頂點v)· 有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)· 邊權可正可負(如有負權回路輸出錯誤提示)· 差分約束系統(tǒng)(至今貌似只看過一道題)        Bellma

24、n-Ford算法描述：1. 初始化：將除源點外的所有頂點的最短距離估計值 dv +, ds 02. 迭代求解：反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次，看下面的描述性證明(當做樹)）3. 檢驗負權回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false，表明問題無解；否則算法返回true，并且從源點可達的頂點v的最短距離保存在dv中        描述性證明：(這個解釋很好)  

25、0;     首先指出，圖的任意一條最短路徑既不能包含負權回路，也不會包含正權回路，因此它最多包含|v|-1條邊。其次，從源點s可達的所有頂點如果 存在最短路徑，則這些最短路徑構成一個以s為根的最短路徑樹。Bellman-Ford算法的迭代松弛操作，實際上就是按頂點距離s的層次，逐層生成這棵最短路徑樹的過程。在對每條邊進行1遍松弛的時候，生成了從s出發(fā)，層次至多為1的那些樹枝。也就是說，找到了與s至多有1條邊相聯(lián)的那些頂點的最短路徑；對每條邊進行第2遍松弛的時候，生成了第2層次的樹枝，就是說找到了經過2條邊相連的那些頂點的最短路徑。因為最短路徑最多只包含

26、|v|-1條邊，所以，只需要循環(huán)|v|-1 次。每實施一次松弛操作，最短路徑樹上就會有一層頂點達到其最短距離，此后這層頂點的最短距離值就會一直保持不變，不再受后續(xù)松弛操作的影響。（但是，每次還要判斷松弛，這里浪費了大量的時間，這就是Bellman-Ford算法效率底下的原因，也正是SPFA優(yōu)化的所在）。，如圖(沒找到畫圖工具的射線)，若是B和C的最短路徑不更新，那么點D的最短路徑肯定也無法更新，這就是優(yōu)化所在。如果沒有負權回路，由于最短路徑樹的高度最多只能是|v|-1，所以最多經過|v|-1遍松弛操作后，所有從s可達的頂點必將求出最短距離。如果 dv仍保持 +，則表明從s到v不可達。如果有負權

27、回路，那么第 |v|-1 遍松弛操作仍然會成功，這時，負權回路上的頂點不會收斂。           參考了圖論。        問題：Bellman-Ford算法是否一定要循環(huán)n-1次么？未必！其實只要在某次循環(huán)過程中，考慮每條邊后，都沒能改變當前源點到所有頂點的最短路徑長度，那么Bellman-Ford算法就可以提前結束了(開篇提出的小優(yōu)化就是這個)。        上代碼(參考了牛

28、帥的博客)#include<iostream>#include<cstdio>using namespace std;#define MAX 0x3f3f3f3f#define N 1010int nodenum, edgenum, original; /點，邊，起點typedef struct Edge /邊 int u, v; int cost;Edge;Edge edgeN;int disN, preN;bool Bellman_Ford() for(int i = 1; i <= nodenum; +i) /初始化 disi = (i = original

29、 ? 0 : MAX); for(int i = 1; i <= nodenum - 1; +i) for(int j = 1; j <= edgenum; +j) if(disedgej.v > disedgej.u + edgej.cost) /松弛（順序一定不能反） disedgej.v = disedgej.u + edgej.cost; preedgej.v = edgej.u; bool flag = 1; /判斷是否含有負權回路 for(int i = 1; i <= edgenum; +i) if(disedgei.v > disedgei.u + edgei.cost) flag = 0; break; return flag;void print_path(int root) /打印最短路的路徑（反向） while(root != preroot) /前驅 print