戴克斯特拉演算法
戴克斯特拉演算法(英語:Dijkstra's algorithm),又稱迪傑斯特拉演算法、Dijkstra演算法[6],是由荷蘭電腦科學家艾茲赫爾·戴克斯特拉在1956年發現的演算法,並於3年後在期刊上發表[7][8][9]。戴克斯特拉演算法使用類似廣度優先搜尋的方法解決賦權圖[9]的單源最短路徑問題[10][1][2]。
戴克斯特拉演算法 | |
---|---|
概況 | |
類別 | 搜尋演算法[1][2] 貪婪演算法[1] 動態規劃[3] |
資料結構 | 圖 堆/優先佇列(演算法最佳化)[1][4] |
複雜度 | |
最壞時間複雜度 | (使用斐波那契堆最佳化的戴克斯特拉演算法)[5][4] |
空間複雜度 | (使用鄰接表儲存邊的情況)[1] |
相關變數的定義 | |
代表圖中邊數,代表圖中節點個數,為目前所有實際最短路徑值不確定節點的集合,為目前所有實際最短路徑值確定節點的集合,為到某點的最短路徑估計,為到某點的最短路徑實際值,為邊集中邊的最大權值。 |
該演算法存在很多變體:戴克斯特拉的原始版本僅適用於找到兩個頂點之間的最短路徑[9],後來更常見的變體固定了一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑,產生一個最短路徑樹[1]。
該演算法解決了圖 上帶權的單源最短路徑問題[1][11]:196–206。具體來說,戴克斯特拉演算法設置了一頂點集合,在集合中所有的頂點與源點之間的最終最短路徑權值均已確定[1]。演算法反覆選擇最短路徑估計最小的點並將加入中[1]。該演算法常用於路由演算法或者作為其他圖演算法的一個子模組[12]。舉例來說,如果圖中的頂點表示城市,而邊上的權重表示城市間開車行經的距離,該演算法可以用來找到兩個城市之間的最短路徑[8][2]。
描述
戴克斯特拉演算法通過保留目前為止所找到的每個頂點 從 到 的最短路徑來工作[1][2]。初始時,原點 的路徑權重被賦為 0 (即原點的實際最短路徑=0)[1][2]。同時把所有其他頂點的路徑長度設為無窮大,即表示我們不知道任何通向這些頂點的路徑[1]。當演算法結束時, 中儲存的便是從 到 的最短路徑,或者如果路徑不存在的話是無窮大[1]。
鬆弛操作是戴克斯特拉演算法的基礎操作:如果存在一條從 到 的邊,那麼從 到 的一條新路徑是將邊 添加到從 到 的路徑尾部來拓展一條從 到 的路徑[1][9]。這條路徑的長度是 [1]。如果這個值比目前已知的 的值要小,那麼可以用這個值來替代當前 中的值[1]。鬆弛邊的操作一直執行到所有的 都代表從 到 的最短路徑的長度值[1]。
演算法維護兩個頂點集合 和 [1][9]。集合 保留所有已知實際最短路徑值的頂點,而集合 則保留其他所有頂點[1][9]。集合 初始狀態為空,而後每一步都有一個頂點從 移動到 [1][9]。這個被選擇的頂點是 中擁有最小的 值的頂點[1][2]。當一個頂點 從 中轉移到了 中,演算法對 的每條外接邊 進行鬆弛[1]。
《演算法導論》中給出了以下偽代碼[1]:該偽代碼計算並保留圖 中原點 到每一頂點 的最短距離 。其中,函數 將頂點集合 中有最小 值的頂點 從 中刪除並返回 [1]。
1 function Dijkstra(G, w, s) 2 INITIALIZE-SINGLE-SOURCE(G, s) //實際上的操作是將每個除原點外的頂點的 置為無窮大, 3 4 // 是頂點 的一個優先佇列,以頂點的最短路徑估計排序 5 while( ) 6 do //選取 為 中最短路徑估計最小的頂點 7 8 for each vertex v 9 do RELAX(u, v, w) //鬆弛成功的節點會被加入到佇列中
如果我們只對在 和 之間尋找一條最短路徑的話,我們可以在第5或第6行添加條件如果滿足 的話終止程式[1][2]。
在肯尼·羅森所著的《離散數學及其應用》中給出了如下的另一份偽代碼[2]:
1 procedure Dijkstra(G:邊全為正權的圖) 2 {G帶有頂點 和若干邊 } 3 for to n 4 5 6 7 while 8 begin 9 不屬於 的 最小的一個頂點 10 11 for 所有不屬於 的頂點 12 if then 13 end{ 從a到z的最短路長度}
在該 演算法演示頁面 (頁面存檔備份,存於互聯網檔案館),可以自訂節點,邊的權重等資訊,然後觀察演算法每一步的執行過程。
時間複雜度
我們可以用大O符號將該演算法的運行時間表示為邊數 和頂點數 的函數[1]。
對於任何基於頂點集 的實現,演算法的執行時間是 ,其中 和 分別表示完成鍵的降序排列時間和從 中提取最小鍵值的時間[1]。
對於沒有任何最佳化的戴克斯特拉演算法,實際上等價於每次遍歷了整個圖的所有節點來找到Q中滿足條件的元素(即尋找最小的頂點是 的),此外實際上還需要遍歷所有的邊一遍,因此演算法的複雜度是 [2]。
對於邊數少於 的稀疏圖來說,可以用鄰接表來更有效的實現該演算法[1]。
可以使用一個二叉堆積或者斐波納契堆用作優先隊列來尋找最小的頂點( )以最佳化演算法[14][15]。當用到二叉堆積的時候,演算法所需的時間為 [14],斐波納契堆能提高一些效能,讓演算法運行時間達到 [4][15]。然而,使用斐波納契堆進行編程,有時會由於演算法常數過大而導致速度沒有顯著提高[16]。
下面是一些戴克斯特拉演算法經典實現的複雜度比較:
演算法 | 最壞時間複雜度 | 發現者(按照論文發表時間從前向後排序) |
---|---|---|
使用鄰接表的戴克斯特拉演算法 | 萊索雷克及格雷等人[17],艾茲赫爾·戴克斯特拉[9],明蒂[18],懷廷及希利爾[19] | |
使用二叉堆積最佳化的戴克斯特拉演算法 | 唐納德·約翰遜[14] | |
使用斐波那契堆最佳化的戴克斯特拉演算法 | 米高·弗雷德曼及羅伯特·塔揚[4][15] | |
唐納德·約翰遜[20],洛夫·卡爾松及帕特里西奧·波夫萊特[21] |
正確性證明
《演算法導論》使用迴圈不變式(數學歸納法)給出了如下的一份證明[1]:
- 已知一帶權圖 ,其加權函數 的值非負,源點為 。對該圖執行戴克斯特拉演算法,對所有 有 。其中 表示u點的最短路徑估計, 表示 到 點的最短路徑。
- 證明:證明如下的迴圈不變式成立即可:在每次執行EXTRACT-MIN時,對每個頂點 ,有 成立即可。由於上界性質,在 加入了 之後,一旦有 ,則在後面的每次迴圈中都不會改變這個性質。
- 初始化:第一次迴圈前, ,因此迴圈不變式顯然成立。
- 保持:實際上要證明每一輪迴圈中加入到 中的節點滿足 。利用反證法,假設 是第一個不滿足此條件的節點,考慮迴圈開始前的狀況,首先 一定不等於 ,這是顯然的。其次 一定有到 的路徑,否則路徑為無窮大。那麼假設在 進入時,有最短路徑 ,假設該路徑上存在兩個點 , 。 、 ,且x是y的前驅,路徑 可以分解為 (此處 表示經過 這條路徑,後同),其中路徑 和路徑 可以為空。由於 是第一個不滿足 的,又因為 是滿足該條件的,而且 一定已經被鬆弛過了,所以 是滿足該條件的。
- 現在只需要推出矛盾,即可證明u不存在: 在 之前出現,而且圖中所有權值非負,因此有 ,所以:
,但是由於 和 同時在 中,因此 ,因此必有 ,也就證明了 點不可能不滿足該條件,上述假設為假,原命題得證。 - 終止:終止時, ,由於 ,因此 ,因此對所有 有 。
起源與歷史
從鹿特丹到格羅寧根的最短路徑是什麼?實際上,這就是對於任意兩座城市之間的最短路問題。解決這個問題實際上大概只花了我20分鐘:一天早上,我和我的未婚妻在阿姆斯特丹購物,累了,我們便坐在咖啡館的露台上喝咖啡,然後我就試了一下能否用一個演算法解決最短路問題。正如我所說,這是一個20分鐘的發現。不過實際上,我在3年後的1959年才把這個演算法發表在論文上。即使現在來看這篇論文的可讀性也非常高,這個演算法之所以如此優雅,其中一個原因就是我沒用筆紙就設計了它。後來我才知道,沒用筆紙設計的優點之一是你不得不避免所有可避免的複雜問題。令我驚訝的是,這個演算法最終成為我成名的基石之一。
——艾茲赫爾·戴克斯特拉在2001年的採訪中提到戴克斯特拉演算法的發現歷程[8]
戴克斯特拉1956年在荷蘭數學和電腦科學研究學會擔任程式設計師時為了展示新型電腦ARMAC的功能曾思考過最短路徑問題的解法[22]。他的目標是讓不去實際計算的人也能理解這個問題和解決的方法,於是他在發現了這個演算法之後在ARMAC上做了簡單實驗[8]。1959年,他正式將此演算法發表在期刊上,該演算法也成為了戴克斯特拉成名的基石之一[8][9]。
相關應用
鏈路狀態路由協定中需要計算最短路時常常要用到該演算法,該演算法在開放最短路徑優先和中間系統到中間系統協定中的相關應用是其在網絡路由中的典型實現[12]。
戴克斯特拉演算法及其改進演算法應用廣泛,尤其是在尋路、交通、規劃中[23][24][25][26]。
如果有已知資訊可用來估計某一點到目標點的距離,則可改用A*搜尋演算法,以減小最短路徑的搜尋範圍,戴克斯特拉演算法本身也可以看作是A*搜尋演算法的一個特例[27][28]。
戴克斯特拉演算法本身採用了與Prim演算法類似的貪心策略[9][29][30][31]。快速行進演算法與戴克斯特拉演算法同樣有相似之處[32]。
參考源程式
以下是該演算法使用堆最佳化的一個C++實現參考[33]:
// 無向圖
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
// iPair ==> Integer Pair(整数对)
typedef pair<int, int> iPair;
// 加边
void addEdge(vector<pair<int, int>> adj[], int u, int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// 计算最短路
void shortestPath(vector<pair<int, int>> adj[], int V, int src)
{
// 关于stl中的优先队列如何实现,参考下方网址:
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
// 距离置为正无穷大
vector<int> dist(V, INF);
vector<bool> visited(V, false);
// 插入源点,距离为0
pq.push(make_pair(0, src));
dist[src] = 0;
/* 循环直到优先队列为空 */
while (!pq.empty())
{
// 每次从优先队列中取出顶点事实上是这一轮最短路径权值确定的点
int u = pq.top().second;
pq.pop();
if (visited[u])
{
continue;
}
visited[u] = true;
// 遍历所有边
for (auto x : adj[u])
{
// 得到顶点边号以及边权
int v = x.first;
int weight = x.second;
// 可以松弛
if (dist[v] > dist[u] + weight)
{
// 松弛
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// 打印最短路
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
int main()
{
int V = 9;
vector<iPair> adj[V];
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);
shortestPath(adj, V, 0);
return 0;
}
以下是該演算法Python的一個實現:
import sys
max = sys.maxsize
vertices_number = 6
adjacency_matrix = [
[0, 1, 10, -1, -1, 2],
[10, 0, 1, -1, -1, -1],
[1, 10, 0, -1, -1, -1],
[-1, -1, 2, 0, 1, 10],
[-1, -1, -1, 10, 0, 1],
[-1, -1, -1, 1, 10, 0]]
start = []
dest = ["2", "5"]
key = []
def init_keys(s: int):
global key
key = [ max ] * vertices_number
key[s] = 0
def dijkstra(from_vertex, dest_vertex):
fid = int(from_vertex) - 1
tid = int(dest_vertex) - 1
init_keys(fid)
rel = [fid]
min_vertex = fid
hop_path = {}
while len(rel) <= vertices_number and min_vertex != tid:
for i in range(vertices_number):
if i != min_vertex and i not in rel and \
adjacency_matrix[min_vertex][i] > 0 \
and key[i] > key[min_vertex] + adjacency_matrix[min_vertex][i]:
key[i] = key[min_vertex] + adjacency_matrix[min_vertex][i]
hop_path.update({i + 1: {"from": min_vertex + 1, "cost": adjacency_matrix[min_vertex][i]}})
if min_vertex not in rel:
rel.append(min_vertex)
min_vertex = tid
for i in range(vertices_number):
if i not in rel and key[i] < key[min_vertex]:
min_vertex = i
if len(hop_path) == 0 or int(dest_vertex) not in hop_path:
return -1, -1
else:
next_hop = int(dest_vertex)
path_str = dest_vertex
while hop_path[next_hop]["from"] != int(from_vertex):
cost = hop_path[next_hop]["cost"]
next_hop = hop_path[next_hop]["from"]
path_str = "{} -({})-> {}".format(str(next_hop), cost ,path_str)
path_str = "{} -({})-> {}".format(str(hop_path[next_hop]["from"]), hop_path[next_hop]["cost"], path_str)
return key[tid], path_str
def find_shortest_router():
for s in start:
print("Forwarding Table for {}".format(s))
print("{:>10} {:>10} {}".format("To", "Cost", "Path"))
for d in dest:
c, n = dijkstra(s, d)
print("{:>10} {:>10} {}".format(d, c, n))
def main():
for i in range(1, vertices_number + 1):
if str(i) not in dest:
start.append(str(i))
find_shortest_router()
if __name__ == '__main__':
main()
參見
參考
參考文獻
- ^ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 24.3: Dijkstra's algorithm. Introduction to Algorithms Second. MIT Press and McGraw–Hill. 2001: 595–601. ISBN 0-262-03293-7.
- ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill College. 2002. ISBN 0-07-293033-0.
- ^ 有爭議,見:Moshe Sniedovich. Dijkstra's algorithm revisited: the dynamic programming connexion. Control and Cybernetics. 2006, 35: 599–620 [2020-03-04]. (原始內容存檔於2020-03-04).等
- ^ 4.0 4.1 4.2 4.3 Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE: 338–346. 1984. doi:10.1109/SFCS.1984.715934.
- ^ Andrew V. Goldberg; Robert E. Tarjan. Expected performance of Dijkstra’s shortest path algorithm. NEC Research Institute Report. 1996年 [2019-12-12]. (原始內容存檔於2021-11-22).
- ^ 樂陽、龔健雅. Dijkstra最短路径算法的一种高效率实现. 《科學技術創新》. 2020, (17): 75–77 [2020-06-30]. (原始內容存檔於2021-02-13).
- ^ Richards, Hamilton. Edsger Wybe Dijkstra. A.M. Turing Award. Association for Computing Machinery. [2017-10-16]. (原始內容存檔於2017-10-21).
At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?
- ^ 8.0 8.1 8.2 8.3 8.4 Frana, Phil. An Interview with Edsger W. Dijkstra. Communications of the ACM. August 2010, 53 (8): 41–47. doi:10.1145/1787234.1787249.
- ^ 9.00 9.01 9.02 9.03 9.04 9.05 9.06 9.07 9.08 9.09 9.10 Dijkstra, E. W. A note on two problems in connexion with graphs (PDF). Numerische Mathematik. 1959, 1: 269–271 [2020-01-27]. doi:10.1007/BF01386390. (原始內容存檔 (PDF)於2020-01-23).
- ^ 10.0 10.1 Felner, Ariel. Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm. Proc. 4th Int'l Symp. on Combinatorial Search. 2011 [2020-02-18]. (原始內容存檔於2020-02-18).
- ^ Mehlhorn, Kurt; Sanders, Peter. Chapter 10. Shortest Paths (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. 2008 [2020-02-14]. ISBN 978-3-540-77977-3. doi:10.1007/978-3-540-77978-0. (原始內容存檔 (PDF)於2021-02-24).
- ^ 12.0 12.1 H. Ishikawa, S. Shimizu, Y. Arakawa, N. Yamanaka, K. Shiba. New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2. IEEE. 13 August 2007 [2020-03-21]. doi:10.1109/ICC.2007.332. (原始內容存檔於2020-12-18).
- ^ Yefim, Dinitz; Rotem, Itzhak. Hybrid Bellman–Ford–Dijkstra algorithm,. Journal of Discrete Algorithms. 2017, 42: 35–44. doi:10.1016/j.jda.2017.01.001.
- ^ 14.0 14.1 14.2 Johnson, Donald B. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM. 1977, 24 (1): 1–13. doi:10.1145/321992.321993.
- ^ 15.0 15.1 15.2 Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the Association for Computing Machinery. 1987, 34 (3): 596–615 [2018-04-03]. doi:10.1145/28869.28874. (原始內容存檔於2006-04-28).
- ^ Skiena, Steven. The Algorithm Design Manual (PDF) 2. Springer. 2008-07-26: 212 [2015-04-11]. ISBN 978-0073523408. doi:10.1007/978-1-84800-070-4. (原始內容 (PDF)存檔於2015-06-09) (英語).
- ^ Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology. 1957.
- ^ 見Pollack, Maurice; Wiebenson, Walter. Solution of the Shortest-Route Problem—A Review. Oper. Res. March–April 1960, 8 (2): 224–230. doi:10.1287/opre.8.2.224. Attributes Dijkstra's algorithm to Minty ("private communication") on p.225.
- ^ Whiting, P. D.; Hillier, J. A. A Method for Finding the Shortest Route through a Road Network. Operational Research Quarterly. March–June 1960, 11 (1/2): 37–40. doi:10.1057/jors.1960.32.
- ^ Johnson, Donald B. A priority queue in which initialization and queue operations take O(log log D) time. Mathematical Systems Theory. December 1981, 15 (1): 295–309. MR 0683047. doi:10.1007/BF01786986.
- ^ Karlsson, Rolf G.; Poblete, Patricio V. An O(m log log D) algorithm for shortest paths. Discrete Applied Mathematics. 1983, 6 (1): 91–93. MR 0700028. doi:10.1016/0166-218X(83)90104-X.
- ^ ARMAC. Unsung Heroes in Dutch Computing History. 2007. (原始內容存檔於2013-11-13).
- ^ Sven Peyer; Dieter Rautenbach,Jens Vygen. A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing. Journal of Discrete Algorithms. 2007, 7 (4): 377–390. doi:10.1016/j.jda.2007.08.003.
- ^ Ismail Rakip Karas,Sait Demir. Dijkstra algorithm interactive training software development for network analysis applications in GIS (PDF). Energy Education Science and Technology Part A: Energy Science and Research. 2011, 28: 445–452 [2020-03-04]. (原始內容存檔 (PDF)於2020-03-04).
- ^ Dean Djokic,David R. Maidment. Application of GIS Network Routines for Water Flow and Transport. Journal of Water Resources Planning and Management. 1993, 119 (2). doi:10.1061/(ASCE)0733-9496(1993)119:2(229).
- ^ 江琦浩. 迪杰斯特拉算法在企业成本控制研究中的应用. 中國商貿. 2012, (03X) [2020-12-24]. (原始內容存檔於2021-02-13).
- ^ De Smith, Michael John; Goodchild, Michael F.; Longley, Paul, Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools, Troubadour Publishing Ltd: 344, 2007 [2020-03-04], ISBN 9781905886609, (原始內容存檔於2017-02-27).
- ^ Hetland, Magnus Lie, Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress: 214, 2010 [2020-03-04], ISBN 9781430232377, (原始內容存檔於2017-02-28).
- ^ Tarjan, Robert Endre, Data Structures and Network Algorithms, CBMS_NSF Regional Conference Series in Applied Mathematics 44, Society for Industrial and Applied Mathematics: 75, 1983,
The third classical minimum spanning tree algorithm was discovered by Jarník and rediscovered by Prim and Dikstra; it is commonly known as Prim's algorithm.
- ^ Prim, R.C. Shortest connection networks and some generalizations (PDF). Bell System Technical Journal. 1957, 36 (6): 1389–1401 [18 July 2017]. Bibcode:1957BSTJ...36.1389P. doi:10.1002/j.1538-7305.1957.tb01515.x. (原始內容 (PDF)存檔於18 July 2017).
- ^ V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)
- ^ Danielsson, Per-Erik; Lin, Qingfen. A Modified Fast Marching Method. Image Analysis. 24 June 2003: 1154–1161 [2020-03-25]. (原始內容存檔於2021-02-13).
- ^ geeksforgeeks. Dijkstra’s Shortest Path Algorithm using priority_queue of STL. geeksforgeeks. [2020-05-11]. (原始內容存檔於2021-02-13).
擴充閱讀
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 24.3: Dijkstra's algorithm. Introduction to Algorithms second. MIT Press、S&P Global. 2001: 595–601. ISBN 0-262-03293-7.
- Dial, Robert B. Algorithm 360: Shortest-path forest with topological ordering [H]. CACM. 1969, 12 (11): 632–633. doi:10.1145/363269.363610.
- Zhan, F. Benjamin; Noon, Charles E. Shortest Path Algorithms: An Evaluation Using Real Road Networks. Transportation Science. February 1998, 32 (1): 65–73. doi:10.1287/trsc.32.1.65.
- Knuth, D.E. A Generalization of Dijkstra's Algorithm. Information Processing Letters. 1977, 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3.
- Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. Faster Algorithms for the Shortest Path Problem. Journal of Association for Computing Machinery (ACM). April 1990, 37 (2): 213–223. doi:10.1145/77600.77615.
- Raman, Rajeev. Recent results on the single-source shortest paths problem. SIGACT News. 1997, 28 (2): 81–87. doi:10.1145/261342.261352.
- Thorup, Mikkel. On RAM priority Queues. SIAM Journal on Computing. 2000, 30 (1): 86–109. doi:10.1137/S0097539795288246.
- Thorup, Mikkel. Undirected single-source shortest paths with positive integer weights in linear time. journal of the ACM. 1999, 46 (3): 362–394 [2017-11-01]. doi:10.1145/316542.316548. (原始內容存檔於2017-09-21).
- ZHANG Lin-guang,FANG Jin-yun,SHEN Pai-wei. An Improved Dijkstra Algorithm Based on Pairing Heap. Journal of Image and Graphics. 2007-05.
外部連結
- 迪科斯徹演算法分解演示影片(優酷) (頁面存檔備份,存於互聯網檔案館)
- Animation of Dijkstra's algorithm (頁面存檔備份,存於互聯網檔案館)
- The Boost Graph Library (BGL) (頁面存檔備份,存於互聯網檔案館)
- Interactive Implementation of Dijkstra's Algorithm (頁面存檔備份,存於互聯網檔案館)
- Shortest Path Problem: Dijkstra's Algorithm
- Dijkstra演算法使用TDD的一個實現 (頁面存檔備份,存於互聯網檔案館)
- Graphical explanation of Dijkstra's algorithm step-by-step on an example (頁面存檔備份,存於互聯網檔案館)