0%

最短路徑(Shortest Path Problem)

今年是2021,資芽的二階主題跟2020上的有很多的差別,因此會利用暑假把2020的東西也補一補!

課程內容

路徑與權重

  • $G=(V,E)$
  • 尋找最短路徑權重和最小
  • 無帶權:BFS直接做(or DFS)
  • 有帶權最短路徑

Floyd-Warshall:全點對最短路徑(All Pairs)

  • 不支援負環

  • 想法: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次的worst case:
    • 剛好跟最短路徑的順序相反
    • 每次 Relax 後只能優化單一子路徑
    • 共有V個頂點,需要有V-1 條子路徑,每一次一條
    • 檢查負環:做完之後卻有滿足$d[v] > d[u]+w(u,v)$ ,表示有負環

優化:SPFA(Shortest Path Faster Algorithm)

  • 每次只relax更新過的點

  • 使用queue優化,有點像BFS過程

    • 1.把起點 Push 到 Queue
    • 2.從 Queue 裡 Pop 出一筆資料
    • 3.該筆資料的所有邊進行 Relax
    • 4.有更新到的頂點再 Push 到 Queue
    • 5.重複步驟 2 ~ 4,直到 Queue 為空
  • 時間:$O(VE)$ ->worst case,期望 $O(KE)$ ,K大概是2吧(反正挺快的)

DAG Shortest Path

首先對所有點進行拓墣排序,花上時間 $O(V+E)$,接著對每一條邊進行鬆弛,時間$O(E)$,因此總時間複雜度是 $O(V+E)$。這個時間複雜度是很快的,但相對的限制也非常多,除了不能有負邊與負環之外,更不能有正環在其中,否則不能進行拓墣排序(在之前筆記進階圖論(一))有提到,也就是這一中圖必須是DAG(Directed Acyclic Graph)!

一個有趣的應用:PERT

最短路徑樹

  • 紀錄predecessor(樹父節點唯一)

  • 起點到每個點的最短路徑都唯一的話,那把這些路徑疊起來會變成一棵樹

  • 樹:每一點都有唯一來源(最短路)

最短路徑比較

最短路徑問題共有以下求解方式(當然還有一堆),整理比較圖:

負環

上表中的可以處理負環的SPFA和Bellman-Ford是以什麼樣的方式處理?(遇到負環權重應該是$-\infty$)上方所謂負環是指下圖這種情況(當出發點為s,終點為t求最短路徑的問題),因為沒有經過負環,因此 $\delta(s,t)$ 可以被SPFA和Bellman-Ford求出正確的最短路徑為1。我們可以利用從終點回朔最短路徑(利用predecessor紀錄)看是否有重複經過的點,如果有則表示途中有經過負環!

至於其他的算法,都會求出不正確的數值!

Floyd warshall
這個演算法是處理全點對的最短路徑,如果有負環,那一定有任兩點的最短距離是錯誤的。不過我們一樣可以利用Floyd-Warshall演算法判斷圖中是否有負環,只要檢查每一個點走到自己的距離是否為負 ,即$dis[i][i]<0$ 是否成立,如果成立表示圖中有負環。

Dijkstra
這個演算法要求的限制更多,圖中不可以有負邊(更別提多個負邊組成的赴環),原因是在Dijkstra求最短路的過程中使用到貪心的想法,當我們從heap裡面取出目前距離最短的點之後,便不會再次被更新。如果有負邊的話,貪心法的過程會發生錯誤,導致得到不正確的答案。

此圖中如果邊 $\delta(B,A)$ 為一負邊,當A被移出集合U中便不會有任何再次被更新的機會,但卻因為這條負邊的關係,導致從$s$到$A$的最短距離並不會被正確更新到!

以上大概就是最短距離的演算法整理,還有一個全點對最短路徑Johnson’s Algorithm,大概就是對任一點做 Bellman-Ford(順便判斷有沒 有負環),得到點權之後,用調整完的邊權做 V 次 Dijkstra,可以比Floyd-Warshall有更好的表現,到時候看。