迪科斯彻算法

维基百科,自由的百科全书
跳转至: 导航搜索
戴克斯特拉算法演示

戴克斯特拉算法英语Dijkstra's algorithm)是由荷兰计算机科学家艾茲赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。舉例來說,如果圖中的頂點表示城市,而邊上的權重表示著城市間開車行經的距離,该演算法可以用來找到兩個城市之間的最短路徑。

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

最初的戴克斯特拉算法不采用最小优先级队列,时间复杂度是O(|V|^2)(其中|V|图的顶点个数)。通过斐波那契堆实现的迪科斯彻算法时间复杂度是O(|E|+|V|\log|V|) (其中|E|是边数) (Fredman & Tarjan 1984)。对于不含负权的有向图,这是目前已知的最快的单源最短路径算法。

算法描述[编辑]

這個算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。初始時,原點 s 的路徑長度值被賦為 0 (d[s] = 0),若存在能直接到达的边(s,m),则把d[m]设为w(s,m),同時把所有其他(s不能直接到达的)頂點的路徑長度設為無窮大,即表示我們不知道任何通向這些頂點的路徑(對於 V 中所有頂點 vs 和上述 md[v] = ∞)。當算法結束時,d[v] 中儲存的便是從 sv 的最短路徑,或者如果路徑不存在的話是無窮大。 Dijkstra 算法的基礎操作是邊的拓展:如果存在一條從 uv 的邊,那麼從 sv 的最短路徑可以通過將邊(u, v)添加到尾部來拓展一條從 s 到 v 的路徑。這條路徑的長度是 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                    // 紀錄前趨頂點

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

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

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 就是從 st 的最短路徑的頂點集。

時間複雜度[编辑]

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

对于基于顶点集Q的实现,算法的运行时间是 O(|E| \cdot dk_Q + |V| \cdot em_Q),其中dk_Qem_Q分别表示完成键的降序排列时间和从Q中提取最小键值的时间。

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

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

相關問題及演算法[编辑]

原本的该演算法還能夠加以修改以擴充其功能。舉例來說,面對一個問題,有時我們可能希望取得數學上的次佳解。為了求得這些次佳解,首先先用原本的该演算法求出最佳路徑;接下來,我們移除最佳路徑中任一段路徑,並對剩下來的子集合圖再做一次最佳路徑計算。對於最佳路徑上的每一段路徑做一樣的操作,我們可以得到許多次佳路徑解,將這些路徑排序後即為原路徑問題的次佳路徑解集合。

開放最短路徑優先算法是该算法在網絡路由中的一個具體實現。

與 Dijkstra 算法不同,Bellman-Ford算法可用於具有負花費邊的圖,只要圖中不存在總花費為負值且從源點 s 可達的環路(如果有這樣的環路,則最短路徑不存在,因為沿環路循環多次即可無限制的降低總花費)。

與最短路徑問題相關最有名的一個問題是旅行商問題,此類問題要求找出恰好通過所有目標點一次且最終回到原點的最短路徑。然而該問題為NP-完全的;換言之,與最短路徑問題不同,旅行商問題不太可能具有多項式時間解法。

如果有已知信息可用來估計某一點到目標點的距離,則可改用A*搜尋算法,以減小最短路徑的搜索範圍。

參考[编辑]

外部鏈接[编辑]