Single Source Shortest Paths: Label Correcting Algorithm

用途

一張有向圖,選定一個起點,找出起點到圖上各點的最短路徑,即是找出其中一棵最短路徑樹。可以順便偵測起點是否會到達負環,然後找出其中一個負環。

想法

當最短路徑只有正邊和零邊,截去末端之後,仍是最短路徑,而且長度一定更短。當有負邊,長度不會更短,反而更長。

圖上有負邊,則無法使用Label Setting Algorithm。當下不在樹上、離根最近的點,以後不見得是最短路徑。

圖上有負邊,就必須使用Label Correcting Algorithm。即使數值標記錯誤了,仍可修正。

Label Setting Algorithm只有正邊、零邊,知道relaxation的正確順序,逐步設定每個點的最短路徑長度。

Label Correcting Algorithm受負邊影響,不知道relaxation的正確順序,只好不斷修正每個點的最短路徑長度,直到正確為止。

演算法

由起點開始,不斷朝鄰點拓展,不斷修正鄰點的最短路徑長度,其中必然涵蓋到最短路徑樹的點與邊。拓展過程當中,儘管無法確定最短路徑樹的長相,但是可以確定最短路徑樹正在一層一層生長。

一條最短路徑頂多V-1條邊,一棵最短路徑樹頂多V層。拓展鄰點V-1層之後,必能完成最短路徑樹。

時間複雜度

圖的資料結構為Adjacency Lists,每一層最多有V個點、E條邊,最多拓展V-1層(遭遇負環則是V層),時間複雜度O((V+E) ⋅ V) = O(V² + VE),通常簡單寫成O(VE)。

圖的資料結構為Adjacency Matrix,便是O(V³)。

演算法:找出一棵最短路徑樹

令w[a][b]是a點到b點的距離(即是邊的權重)。
令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都設為無限大。

一、起點塞入queue。
二、重複下面這件事,直到queue沒有東西為止:
 甲、queue彈出一點,做為a點。
   加速:如果queue已有parent[a],則捨棄a點,並且重新彈出一點。
 乙、找到一條邊ab:d[a] + w[a][b] < d[b]。
 丙、以邊ab來修正起點到b點的最短路徑:d[b] = d[a] + w[a][b]。
 丁、b點塞入queue。
   加速:如果queue已有b點,則不塞入。

演算法:偵測起點是否會到達負環

最短路徑一旦經過負環,就會不斷地繞行負環,最短路徑長度成為無限短。

如果沒有經過負環,一條最短路徑最多只有V-1條邊;如果經過負環,一條最短路徑就有無限多條邊。順手記錄最短路徑的邊數,就能順手偵測負環。

演算法:找出起點可以到達的一個負環

確認負環存在之後,利用parent[]陣列,往回追溯,最短路徑的其中一段一定有著負環。

演算法:偵測負環

額外增加一個超級起點,連向圖上每一個點,以便抵達圖上各處。如此就能偵測整張圖上是否有負環、從圖上找到一個負環。

UVa 10557 10682

Single Source Shortest Paths: Bellman-Ford Algorithm

演算法

Label Correcting Algorithm的平行化版本。

圖上所有點同時(或依序)修正鄰點的最短路徑長度,重覆V-1次。如此一來就省去了queue。

時間複雜度

時間複雜度等同於Label Correcting Algorithm,但是計算時間較長。現行的時間複雜度標記方式,無法區分兩者的快慢差異。

演算法:找出一棵最短路徑樹

令w[a][b]是a點到b點的距離(即是邊的權重)。
令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都設為無限大。

一、重複下面這件事V-1次:
 甲、窮舉邊ab:d[a] + w[a][b] < d[b]。
 乙、以邊ab來修正起點到b點的最短路徑:d[b] = d[a] + w[a][b]。
   (即是圖上所有邊同時進行relaxation。)

演算法:偵測起點是否會到達負環

拓展鄰點V-1層之後,理論上已經找到最短路徑樹了。若還能再修正最短路徑長度,則必有負環。

UVa 558

Single Source Shortest Paths: Randomized Label Correcting Algorithm

演算法

Label Correcting Algorithm的隨機化版本。

不斷隨機嘗試圖上每一條邊,逐步修正最短路徑長度。一條一條的邊總有一天將會連接成一條完整的最短路徑、組合成一棵完整的最短路徑樹。

時間複雜度

亂槍打鳥,曠日廢時,最差時間複雜度O(V!)。不過我不會估計平均時間複雜度。

演算法:找出一棵最短路徑樹

令w[a][b]是a點到b點的距離(即是邊的權重)。
令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都設為無限大。

一、重複下面這件事:
 甲、找到一條邊ab:d[a] + w[a][b] < d[b]。
 乙、以邊ab來修正起點到b點的最短路徑:d[b] = d[a] + w[a][b]。

Single Source Shortest Paths in DAG: Topological Sort

演算法

有向無環圖(Directed Acyclic Graph)只朝一個方向前進,得以依照拓樸順序實施relaxation。

此問題類似「Activity Network」,演算法是Topological Sort與Dynamic Programming。

時間複雜度

兩次Graph Traversal的時間。圖的資料結構為Adjacency Matrix,便是O(V²);圖的資料結構為Adjacency Lists,便是O(V+E)。

演算法:找出一棵最短路徑樹

另一種寫法。

UVa 10000 10166 10350 10917 1083 ICPC 4449

Single Source Shortest Paths: Yen's Algorithm

有向圖可以拆解成一群自環與兩個DAG

索引值一樣、索引值從小往大D+、索引值從大往小D-。自由調整索引值,得到不同的拆法。

演算法

檢查自環是否為負環。若是,演算法結束;若否,自環不影響最短路徑,捨棄之。

每回合先算D+、再算D-,依照拓樸順序實施relaxation,總共V/2回合。時間複雜度O(V/2 ⋅ 2(V+E)) = O(VE)。

一條最短路徑,長度最多V-1。最佳情況是清一色D+或D-,僅一回合。最差情況是D+和D-交錯出現,需要V/2回合。

隨機重排索引值、隨機重製D+和D-,可以避免最差情況,平均V/3回合。但是我不會證明,請見:

《Randomized Speedup of the Bellman-Ford Algorithm》