[ Alg info ] Dijkstra’s algorithm (shortest path problem)

Preface: 
最短路徑問題是圖論研究中的一個經典演算法問題， 旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。 演算法具體的形式包括： 

* 確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。適合使用 Dijkstra演算法。
* 確定終點的最短路徑問題 - 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
* 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
* 全局最短路徑問題 - 求圖中所有的最短路徑。適合使用 Floyd-Warshall演算法。

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」， 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有: 

* Dijkstra演算法
* A*演算法
* Bellman-Ford演算法
* SPFA演算法 (Bellman-Ford演算法的改進版本)
* Floyd-Warshall演算法
* Johnson演算法
* Bi-Direction BFS演算法

Description: 
在一個有向圖形 G=(V,E), G 中的每一個邊都有一個比例常數 W(Weight) 與之對應, 如果想求 G 圖形中某一點V0 到其他頂點的最少 W 總和之值, 這類問題就稱為最短路徑問題 (The shortest path problem). 這裡首先討論單點對全部頂點的最短距離, 而一個頂點到多個頂點通常使用 Dijkstra 演算法求得. 接著會在 Dijkstra's algorithm 用到下面的變數: 

* S: 用來存放處理過的 vertex
* V: Graph 的 vertex 集合
* Q: 存放待處理的 vertex. Q = V - S
* u,v: 過程中代表 edge 的變數
* v.d: 用來記錄從 source vertex 到該 vertex 的最短距離
* v.π: 用來記錄從 source vertex 走到該 vertex 的路徑, 離 vertex 最近的 vertex.

Dijkstra’s algorithm: 
首先來看看這個演算法的 pseudo code: 

view plaincopy to clipboardprint?

1. DIJKSTRA(G, w, s)  
2. 1 INITIALIZE-SINGLE-SOURCE(G, s)  
3. 2 S = ∅  
4. 3 Q = G.V  
5. 4 while Q != ∅  
6. 5     u = EXTRACT-MIN(Q)  
7. 6     S = S ∪ {u}  
8. 7     for each vertex v ∈ G.Adj[u ]  
9. 8         RELAX(u,v, w)  

接著簡單說明該 pseudo code: 

1. INITIALIZE-SINGLE-SOURCE(G, s) 是將 G 中的 vertex 進行初始化 v.d=∞, v.π=nil, s.d=0 (v 代表 graph 中的所有 vertex, s 則是 source vertex)
2. 初始集合 S 為空集合
3. 將 G 中的所有 vertex 加到集合 Q
4. while Q != ∅ - 接著每次處理一個 Q 中的 vertex 直到 Q 為空集合.
5. u = EXTRACT-MIN(Q) - 從 Q 中取出一個 v.d 為最小的 vertex.
6. S = S ∪ {u} - 將取出的 vertex u 加到集合 S
7. for each vertex v ∈ G.Adj[u ] - 將取出的 vertex 重新計算它走得到的 vertex 的最短距離(不在 S 集合中)
8. RELAX(u, v, w) - 將新的計算結果更新到 vertex 並將目前 vertex 加到 S 集合

Example: 
1. 接著我們來看一個範例, 假設有下面 Graph, 我們要計算從 vertex 0 到每一個 vertex 的最短距離. 所以一開始處理 vertex 0 後 S={"0"} ; Q={"1","2","3","4","5"}. 因為 vertex 3 距離最短 (v.d=10), 故取它當作下一個處理的 vertex 
 

2. 在處理 vertex 3 時, 發現原本 vertex 4 的最短路徑為 ∞ > (到 vertex 3 最短路徑 = 10) + (vertex 3 到 vertex 4 的 cost = 15)=25, 故更新 vertex 4 的最短距離 (v.d=25). 此時 S={"0", "3"} ; Q={"1","2","4","5"}, 因為 vertex 4 距離最短, 故取它當作下一個處理的 vertex: 
 

3. 在處理 vertex 4 時, 發現原本 vertex 1 的最短路徑為 50 > (到 vertex 4 最短路徑 = 25) + (vertex 4 到 vertex 1 的 cost = 20)=45, 故更新 vertex 1 的最短距離 (v.d=45). 此時 S={"0", "3", "4"} ; Q={"1","2","5"}, 因為 vertex 1 與 vertex 2 距離最短, 而我們取 vertex 1 作下一個處理: 
 

4. 在處理 vertex 1 時, 唯一會碰到不屬於集合 S 的 vertex 2 並不會使原先 vertex 2 最短路徑變短 ((45+10=55)>45). 此時 S={"0", "1", "3", "4"} ; Q={"2","5"}, 因為 vertex 2 距離最短, 故取它當作下一個處理的 vertex: 
 

5. 在處理 vertex 2 時並部會碰到任何不屬於集合 S 的 vertex. 故不做任何處理; 同樣的剩下的 vertex5 也是如此. 故此時集合 Q 已經成為空集合並結束整個演算法. 
 

Supplement: 
* [ Data Structures with Java ] Section 25.5 : Dijkstra's Minimum-Path Algorithm 
* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (單點對全部頂點) 
* NTU 2013 course - DSA : 4/30 Graph3