戴克斯特拉算法

戴克斯特拉算法（英語：Dijkstra's algorithm）是由荷兰计算机科学家艾茲赫尔·戴克斯特拉（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，该演算法可以用來找到兩個城市之間的最短路徑。

该演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 所有邊的集合，而邊的權重則由權重函數 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負权重（weight）。邊的权重可以想像成兩個頂點之間的距離。任兩點間路徑的权重，就是該路徑上所有邊的权重總和。已知有 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t 的最低权重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。

算法描述

這個算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。初始時，原點 s 的路徑長度值被賦為 0 （d[s] = 0），若存在能直接到达的边（s,m），则把d[m]设为w（s,m）,同時把所有其他（s不能直接到达的）頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於 V 中所有頂點 v 除 s 和上述 m 外 d[v] = ∞）。當算法結束時，d[v] 中儲存的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話是無窮大。 Dijkstra 算法的基礎操作是邊的拓展：如果存在一條從 u 到 v 的邊，那麼從 s 到 v 的最短路徑可以通過將邊（u, v）添加到尾部來拓展一條從 s 到 u 的路徑。這條路徑的長度是 d[u] + w(u, v)。如果這個值比目前已知的 d[v] 的值要小，我們可以用新值來替代當前 d[v] 中的值。拓展邊的操作一直執行到所有的 d[v] 都代表從 s 到 v 最短路徑的花費。這個算法經過組織因而當 d[u] 達到它最終的值的時候每條邊（u, v）都只被拓展一次。

算法維護兩個頂點集 S 和 Q。集合 S 保留了我們已知的所有 d[v] 的值已經是最短路徑的值頂點，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，算法對每條外接邊 (u, v) 進行拓展。

虛擬碼

在下面的演算法中，u := Extract_Min(Q) 在頂點集合 Q 中搜索有最小的 d[u] 值的頂點 u。這個頂點被從集合 Q 中刪除並返回給用戶。

 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]                        // 初始化
 3           d[v] := infinity                                 // 将各点的已知最短距离先设置成无穷大
 4           previous[v] := undefined                         // 各点的已知最短路径上的前趋都未知
 5     d[s] := 0                                              // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set                      // Dijkstra演算法主體
 9           u := Extract_Min(Q)
10           S.append(u)
11           for each edge outgoing from u as (u,v)
12                  if d[v] > d[u] + w(u,v)             // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
13                        d[v] := d[u] + w(u,v)               // 更新路径长度到更小的那个和值。
14                        previous[v] := u                    // 记录前趋顶点

如果我們只對在 s 和 t 之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足 u = t 的話終止程序。

通过推导可知，为了记录最佳路径的轨迹，我们只需记录该路径上每个点的前趋，即可通过迭代來回溯出 s 到 t 的最短路徑（当然，使用后继节点来存储亦可。但那需要修改代码）：

1 s := empty sequence 
2 u := t
3 while defined u                                        
4       insert u to the beginning of S
5       u := previous[u]      //previous数组即为上文中的p

現在序列 S 就是從 s 到 t 的最短路徑的頂點集。

時間複雜度

我們可以用大O符號將该算法的運行時間表示為邊數 m 和頂點數 n 的函數。

Dijkstra 算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合 Q，所以搜索 Q 中最小元素的運算（Extract-Min(Q)）只需要線性搜索 Q 中的所有元素。這樣的話算法的運行時間是 O(n²)。

對於邊數少於 n² 的稀疏圖來說，我們可以用鄰接表來更有效的實現该算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點（Extract-Min）。當用到二叉堆的時候，算法所需的時間為O((m + n)log n)，斐波納契堆能稍微提高一些性能，讓算法運行時間達到O(m + n log n)。然而，使用斐波納契堆进行编程，常常会由于算法常数过大而导致速度没有显著提高。

參考

E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp. 595–601.

外部鏈接

算法描述

虛擬碼

時間複雜度

相關問題及演算法

參考

外部鏈接