2020資訊之芽—最短路徑(Shortest Path) | Peienwu 演算法筆記

... 因此會利用暑假把2020的東西也補一補！ 課程內容路徑與權重$G=(V,E)$ 尋找最短路徑權重和最小無帶權：BFS直接做(or DFS) 有帶權最短路徑. 0% 今年是2021，資芽的二階主題跟2020上的有很多的差別，因此會利用暑假把2020的東西也補一補！ 課程內容路徑與權重 $G=(V,E)$ 尋找最短路徑權重和最小 無帶權：BFS直接做(orDFS) 有帶權最短路徑 Floyd-Warshall：全點對最短路徑(AllPairs) 不支援負環 想法：DP轉移（三個迴圈中點、起點、終點依序鬆弛） $d[i][j]=mid(d[i][j],d[i][k]+d[I][k]+d[k][j])$ 如果改寫成定義$dp[k][i][j]$為點$i$走到點$j$，只能經過前k個點的最短路 則轉移：$d[k+1][i][j]=min(d[k][i][j],d[k][i][k+1]+d[k][k+1][j])$ 因此中間點k必須在最外層（不過有論文指出順序顛倒一樣可以得到正確解） 優點：實作容易，缺點：時間$O(v^3)$、無法處理負環（可處理負邊） Dijkstra’s：單點源最短路徑 優點：時間$O(E+V^2)$、無法處理負邊 想法：Greedy（和DP） 維護：1.未拜訪的節點集合$U$2.$d[i]$目前起點到$i$最短路3.目前考慮節點$p$ 重複以下動作直到u為空： 對於所有與$p$連接的節點$q$，$d[q]=min(d[q],d[p]+weight[p][q])$ 當$p$相鄰節點都走過：在$u$中移除$p$ 將$p$更新成U中離起點距離最短的點$min(d[j])$ 可以變成$O((E+V)logV)$->邊較為稀疏的圖時有利（使用priority_queue） 不能處理負邊，因為$d[i]$較小的處理完之後就不會再更動了，加入負邊可能更小 拿距離最小的點$k$去更新其他點，不能保證更新後其他點一定是最短路 上一步走完$k$連接所有邊後，從集合$U$中移除，因為沒有負邊，$k$必定是最短路 Bellman-Ford：單點源最短路徑 可以處理負環 時間：$O(VE)$ 想法：Relax鬆弛 一條邊$\delta(u,v)$滿足$dis[v]=min(dis[v],dis[u]+weight[u][v])$ 對每一條邊進行鬆弛，因為鬆弛沒有按照最短路順序，因此要做V-1次 此為暴力作法 執行V-1次的worstcase： 剛好跟最短路徑的順序相反 每次Relax後只能優化單一子路徑 共有V個頂點，需要有V-1條子路徑，每一次一條 檢查負環：做完之後卻有滿足$d[v]>d[u]+w(u,v)$，表示有負環 優化：SPFA(ShortestPathFasterAlgorithm) 每次只relax更新過的點 使用queue優化，有點像BFS過程 1.把起點Push到Queue 2.從Queue裡Pop出一筆資料 3.該筆資料的所有邊進行Relax 4.有更新到的頂點再Push到Queue 5.重複步驟2~4，直到Queue為空 時間：$O(VE)$->worstcase，期望$O(KE)$，K大概是2吧（反正挺快的） DAGShortestPath首先對所有點進行拓墣排序，花上時間$O(V+E)$，接著對每一條邊進行鬆弛，時間$O(E)$，因此總時間複雜度是$O(V+E)$。

這個時間複雜度是很快的，但相對的限制也非常多，除了不能有負邊與負環之外，更不能有正環在其中，否則不能進行拓墣排序（在之前筆記進階圖論（一））有提到，也就是這一中圖必須是DAG(DirectedAcyclicGraph)！ 一個有趣的應用：PERT 最短路徑樹 紀錄predecessor(樹父節點唯一) 起點到每個點的最短路徑都唯一的話，那把這些路徑疊起來會變成一棵樹 樹：每一點都有唯一來源（最短路） 最短路徑比較最短路徑問題共有以下求解方式（當然還有一堆），整理比較圖： 負環上表中的可以處理負環的SPFA和Bellman-Ford是以什麼樣的方式處理？（遇到負環權重應該是$-\infty$）上方所謂負環是指下圖這種情況（當出發點為s，終點為t求最短路徑的問題），因為沒有經過負環，因此$\delta(s,t)$可以被SPFA和Bellman-Ford求出正確的最短路徑為1。

我們可以利用從終點回朔最短路徑（利用predecessor紀錄）看是否有重複經過的點，如果有則表示途中有經過負環！ 至於其他的算法，都會求出不正確的數值！ Floydwarshall這個演算法是處理全點對的最短路徑，如果有負環，那一定有任兩點的最短距離是錯誤的。

不過我們一樣可以利用Floyd-Warshall演算法判斷圖中是否有負環，只要檢查每一個點走到自己的距離是否為負，即$dis[i][i]<0$是否成立，如果成立表示圖中有負環。

Dijkstra這個演算法要求的限制更多，圖中不可以有負邊（更別提多個負邊組成的赴環），原因是在Dijkstra求最短路的過程中使用到貪心的想法，當我們從heap裡面取出目前距離最短的點之後，便不會再次被更新。

如果有負邊的話，貪心法的過程會發生錯誤，導致得到不正確的答案。

此圖中如果邊$\delta(B,A)$為一負邊，當A被移出集合U中便不會有任何再次被更新的機會，但卻因為這條負邊的關係，導致從$s$到$A$的最短距離並不會被正確更新到！ 以上大概就是最短距離的演算法整理，還有一個全點對最短路徑Johnson’sAlgorithm，大概就是對任一點做Bellman-Ford（順便判斷有沒有負環)，得到點權之後，用調整完的邊權做V次Dijkstra，可以比Floyd-Warshall有更好的表現，到時候看。

文章目錄 本站概要 1.課程內容1.1.路徑與權重1.2.Floyd-Warshall：全點對最短路徑(AllPairs)1.3.Dijkstra’s：單點源最短路徑1.4.Bellman-Ford：單點源最短路徑1.5.優化：SPFA(ShortestPathFasterAlgorithm)1.6.DAGShortestPath1.7.最短路徑樹1.8.最短路徑比較1.9.負環 peienwu Helloworld 24 文章 14 分類 22 標籤 GitHub E-Mail FBPage HackMD