最短路演算法：最短路徑演算法是圖論研究中，一個經典演算法問題；旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑，
確定起點的最短路徑問題：已知起始點，求最短路徑問題，適合使用Dijkstra演算法；（單源最短路徑問題）
全域最短路徑問題：求圖中所有的最短路徑，適用于Floyed-Warshall 演算法；（多源最短路徑問題）
單源最短路徑：給定一個帶權有向圖G=V,E; 其中每條邊是一個實數，另外，還給定V中的一個頂點，稱為源；要計算從源到其他所有頂點的最短路徑長度，這個長度是指路上各邊權之和，這個問題通常稱為單源最短路徑問題；
Dijkstra演算法：Dijkstra演算法使用的是貪心的思想，即在問題求解是總是選擇當前最優解；該演算法用于求解單源最短路問題，不能處理負權，只能用于正權圖中；演算法使用貪心策略，從s0開始，選擇未訪問過v[i]的離s0最近的一個點i，也就是最小的d[i]；然后將i作為中間點，更新經過i,可以到達的點的最短路距離，繼續貪心尋找未訪問過的最近的一個點，經過n次貪心，所有的點訪問完畢，演算法結束；輸出起點和終點間的最短路距離；
- 初始化d[s0]=0,其他d[i]=INF;
- 經過n次貪心，找到起點s0到其他點的最短路距離；
- 貪心：
- 找出一個未訪問過的最小d[k];
- 標記k被訪問過v[k]；
- 將k作為中間點，更新起點s0,到經過k到其他點v的d[v]; 可更新路徑追蹤陣列，記錄當前最短路來自哪一節點 from[v] = k;
- Prim演算法和貪心演算法之間的區別：
- Prim演算法：更新的是未標記集合到已標記集合之間的距離；
- Dijkstra演算法：更新的是源點到未標記集合之間的距離；
- Dijkstra 演算法可以使用堆進行優化：堆優化，Dijkstra演算法的核心是，先找到最小距離，然后在更新；在不優化的時候，我們是通過回圈來找到最小距離的；我們可以使用優先佇列來進行優化；優先佇列一般使用堆來進行實作，所以可以認為是堆優化；C++中有std::priority_queue容器配接器可以來進行使用；
Floyed演算法：Floyed演算法，又稱為插點法，一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的演算法；該演算法可以求出多源最短路，可以處理負權邊情況，但是不能出現負環；該演算法思想使用動態規劃思想；
- 設d[i][j][k]表示i到j只經過1,2,..k這些節點時，i到j的最短路徑，會出現下面兩種情況：
- 經過k點：d[i][j][k] = d[i][k][k-1]+d[k][j][k-1];
- 不經過k點：d[i][j][k]=d[i][j][k-1];
- 狀態轉移方程為：d[i][j][k]=min{d[i][j][k-1], d[i][k][k-1]+d[k][j][k-1]}
- 邊界條件：d[i][j][0]=w[i][j]; (w[i][j]表示，ij邊的權值，不存在邊的權值表示為正無窮)
- 因為k是遞增的，d[i][j]保存的狀態是d[i][j][k-1], 所以可以減少一維，使用二維陣列：
- 狀態轉移方程：d[i][j] = min{d[i][k]+d[k][j], d[i][j]};
- 邊界條件：d[i][j] = w[i][j];
- 列舉k, 使用中間點k來更新i到j的最短路距離；
Bellman-Ford演算法：貝爾曼福特演算法是一種單源最短路演算法；它相對Dijkstra演算法可以進行處理負權，適用前提：沒有負環；實作簡單，但是時間復雜度高；可以用來判斷是否存在負環，每次迭代更新起點到各節點的最短路徑；如果迭代n-1次后(6個點之間存在n-1條邊)，再次迭代還有路徑更新，則說明存在負環；
演算法思想：圖的任意一個條最短路，既不會包含負權回路，也不會包含正權回路，最多包含n-1邊，那么，從源點s開始，可以達到的節點，如果存在最短路，則最短路構成了一顆以s為根的最短路樹，因此，可以按照距離根s的層次，逐層生成達到每個點的最短路（松弛操作）；所以整個程序，就是創建最短路樹的程序；需要一個輔助陣列d[n]和v[n]來記錄最短路距離和跟蹤尋跡；從邊的角度來考慮，每次迭代要遍歷每條邊；回圈n-1次后，第n次回圈如果所有d[n]值不更新，則跳出回圈；如果第n次還存在路徑更新，則說明存在負環；Bellman-Ford演算法也可以求解最長路和用來判斷正環，只要在遞推關系選擇最大的更新就好；
演算法實作程序：
- 初始：dist[u]=INF; dist[s]=0; s為起始點；
- 遞推：對于每條邊（u，v）進行松弛操作；dist[v] = min(dist[v], dist[u]+w[u][v]);(松弛操作為n-1次)
- 最后再回圈一次，判斷是否存在負環；
SPFA演算法：SPFA(Shortest Path Faster Algorithm)；上面描述的Bellman-Ford演算法，演算法時間復雜度比較高；Bellman-Ford演算法需要遞推n次，每次遞推需要掃描所有的邊；然而每次松弛操作并不需要對所有的邊松弛，只需要與當前找到最短路的點相連的邊進行松弛；所以使用佇列，每次將距離更新且不在佇列中的點入隊；每次從佇列中取出一個頂點，對它所有相鄰的節點進行松弛，如果某個頂點松弛成功，如歸該點不在佇列中，則將其入隊，重復這樣的操作，直到佇列為空為止；如果一個節點入隊次數超過n次，說明存在負權回路；可以使用一個cnt[n]陣列來進行計數；
演算法實作程序：
- 初始化：dis[s]=0; dis[i]=INF; 新建一個佇列，將源節點s入隊，標記s已經入隊；
- 從隊首取出一個點u，標記u已經出隊，將與u有邊相連的點進行v進行松弛操作；如果松弛成功并且v不在佇列中，則v入隊；
- 重復上述操作直到佇列為空；
時間復雜度分析：
- Floyed演算法：求多源最短路，可以處理負邊；時間復雜度為O(n3);
- Dijkstra演算法：求單源最短路，不能處理負邊；時間復雜度為O(n2);
- Bellman-Ford演算法：求單源最短路，可以處理負權邊；時間復雜度為O(NM);
- SPFA演算法：求單源最短路，Bellman-ford演算法優化版本，可以處理負權邊；時間復雜度為O(kM)~O(NM); k為較小常數；
代碼實作請參考：https://github.com/yaowenxu/codes/tree/master/最短路演算法
保持更新，轉載請注明出處；更多內容請關注cnblogs.com/xuyaowen;
參考文獻：
最短路問題 四種最短路演算法 dijkstra演算法 Floyd演算法 Prim與Dijkstra演算法的區別 Bellman-Ford演算法 SPFA演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67601.html
標籤：其他