戴克斯特拉算法（英語：Dijkstra's algorithm）由荷蘭計算機科學家艾茲赫爾·戴克斯特拉在1956年提出。迪科斯特拉算法使用了廣度優先搜尋解決賦權有向圖的單源最短路徑問題。該算法存在很多變體；戴克斯特拉的原始版本找到兩個頂點之間的最短路徑，但是更常見的變體固定了一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑，產生一個最短路徑樹。該算法常用於路由算法或者作為其他圖算法的一個子模組。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該算法可以用來找到兩個城市之間的最短路徑。
基本介紹
- 中文名：戴克斯特拉算法
- 外文名：Dijkstra's algorithm
- 領域：數學
簡介,算法描述,時間複雜度,相關問題及算法,
簡介
戴克斯特拉算法（英語：Dijkstra'salgorithm）由荷蘭計算機科學家艾茲赫爾·戴克斯特拉在1956年提出。迪科斯特拉算法使用了廣度優先搜尋解決賦權有向圖的單源最短路徑問題。該算法存在很多變體；戴克斯特拉的原始版本找到兩個頂點之間的最短路徑，但是更常見的變體固定了一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑，產生一個最短路徑樹。該算法常用於路由算法或者作為其他圖算法的一個子模組。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該算法可以用來找到兩個城市之間的最短路徑。
該算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E表示G中所有邊的集合，而邊的權重則由權重函式w:E→[0,∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有V中有頂點s及t，Dijkstra算法可以找到s到t的最低權重路徑(例如，最短路徑)。這個算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。
最初的戴克斯特拉算法不採用最小優先權佇列，時間複雜度是(其中為圖的頂點個數)。通過斐波那契堆實現的迪科斯徹算法時間複雜度是(其中是邊數)（Fredman&Tarjan1984）。對於不含負權的有向圖，這是已知的最快的單源最短路徑算法。
算法描述
這個算法是通過為每個頂點v保留為止所找到的從s到v的最短路徑來工作的。初始時，原點s的路徑權重被賦為0（d[s]=0）。若對於頂點s存在能直接到達的邊（s,m），則把d[m]設為w（s,m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於所有頂點的集合V中的任意頂點v，若v不為s和上述m之一，d[v]=∞）。當算法結束時，d[v]中存儲的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。
邊的拓展是Dijkstra算法的基礎操作：如果存在一條從u到v的邊，那么從s到v的最短路徑可以通過將邊（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]值的頂點v，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d[u]值的頂點。當一個頂點u從Q中轉移到了S中，算法對u的每條外接邊(u,v)進行拓展。
下面的偽代碼計算並保留圖G中原點s到每一頂點v的最短距離d[v]，同時找出並保留v在此最短路徑上的“前趨”，即沿此路徑由s前往v，到達v之前所到達的頂點。其中，函式Extract_Min(Q)將頂點集合Q中有最小d[u]值的頂點u從Q中刪除並返回u。
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的最小距離設為06 S := empty set7 Q := set of all vertices8 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的最短路徑（當然，使用後繼節點來存儲亦可。但那需要修改代碼）：
1s:=emptysequence2u = 3 hile dfined u 4 insert u o th beinning ofS5 :=previous[u] /previous數組即為上文中的p
現在序列S就是從s到t的最短路徑的頂點集。
時間複雜度
我們可以用大O符號將該算法的運行時間表示為邊數m和頂點數n的函式。
對於基於頂點集Q的實現，算法的運行時間是
，其中
和
分別表示完成鍵的降序排列時間和從Q中提取最小鍵值的時間。
Dijkstra算法最簡單的實現方法是用一個鍊表或者數組來存儲所有頂點的集合Q，所以搜尋Q中最小元素的運算（Extract-Min(Q)）只需要線性搜尋Q中的所有元素。這樣的話算法的運行時間是
。
對於邊數少於
的稀疏圖來說，我們可以用鄰接表來更有效的實現該算法。同時需要將一個二叉堆或者斐波納契堆用作優先佇列來查找最小的頂點（Extract-Min）。當用到二叉堆的時候，算法所需的時間為
，斐波納契堆能稍微提高一些性能，讓算法運行時間達到
。然而，使用斐波納契堆進行編程，常常會由於算法常數過大而導致速度沒有顯著提高。
相關問題及算法
與 Dijkstra 算法不同，Bellman-Ford算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點s可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。在可能有環路的情況下，Bellman-Ford算法則可以通過檢測程式while循環次數是否大於|V|來進行判斷。
與最短路徑問題相關最有名的一個問題是旅行商問題，此類問題要求找出恰好通過所有目標點一次且最終回到原點的最短路徑。然而該問題為NP-完全的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間解法。
如果有已知信息可用來估計某一點到目標點的距離，則可改用A*搜尋算法，以減小最短路徑的搜尋範圍。
