戴克斯特拉算法:修订间差异
Tokisaki Kurumi(留言 | 贡献) 小 →算法相关应用 |
Tokisaki Kurumi(留言 | 贡献) |
||
第154行: | 第154行: | ||
[[File:OSPF_area.jpg|thumb|200px|right|一个多区域OSPF网络,在OSPF中使用本算法计算[[最短路径]]]] |
[[File:OSPF_area.jpg|thumb|200px|right|一个多区域OSPF网络,在OSPF中使用本算法计算[[最短路径]]]] |
||
[[開放最短路徑優先]]算法是该算法在網絡[[路由]]中的一個具體實現<ref name=OSPF>{{cite journal |author1=H. Ishikawa, S. Shimizu, Y. Arakawa, N. Yamanaka, K. Shiba |title=New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2 |journal=IEEE |date=13 August 2007 |doi=10.1109/ICC.2007.332 |url=https://ieeexplore.ieee.org/document/4289003}}</ref>。 |
{{tsl|en|Link-state routing protocol|链路状态路由协议}}中需要计算最短路时常常要用到该算法,[[開放最短路徑優先]]算法是该算法在網絡[[路由]]中的一個具體實現<ref name=OSPF>{{cite journal |author1=H. Ishikawa, S. Shimizu, Y. Arakawa, N. Yamanaka, K. Shiba |title=New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2 |journal=IEEE |date=13 August 2007 |doi=10.1109/ICC.2007.332 |url=https://ieeexplore.ieee.org/document/4289003}}</ref>。 |
||
戴克斯特拉算法及其改进算法本身应用广泛,尤其是在[[寻路]]、[[交通]]、[[规划]]中<ref>{{cite journal |author1=Sven Peyer |coauthors=Dieter Rautenbach,Jens Vygen |title=A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing |journal=Journal of Discrete Algorithms |date=2007 |volume=7 |issue=4 |pages=377-390 |doi=10.1016/j.jda.2007.08.003}}</ref><ref>{{cite journal |author1=Ismail Rakip Karas,Sait Demir |title=Dijkstra algorithm interactive training software development for network analysis applications in GIS |journal=Energy Education Science and Technology Part A: Energy Science and Research |date=2011 |volume=28 |pages=445-452 |url=http://web.karabuk.edu.tr/ismail.karas/files/EEST_Part_A_2011_28(1)_445-452.pdf |author= |access-date=2020-03-04 |archive-url=https://web.archive.org/web/20200304070529/http://web.karabuk.edu.tr/ismail.karas/files/EEST_Part_A_2011_28(1)_445-452.pdf |archive-date=2020-03-04 |dead-url=no }}</ref><ref>{{cite journal |author1=Dean Djokic,David R. Maidment |title=Application of GIS Network Routines for Water Flow and Transport |journal=Journal of Water Resources Planning and Management |date=1993 |volume=119 |issue=2 |doi=10.1061/(ASCE)0733-9496(1993)119:2(229)}}</ref><ref>{{cite journal |author1=江琦浩 |title=迪杰斯特拉算法在企业成本控制研究中的应用 |journal=中国商贸}}</ref>。 |
戴克斯特拉算法及其改进算法本身应用广泛,尤其是在[[寻路]]、[[交通]]、[[规划]]中<ref>{{cite journal |author1=Sven Peyer |coauthors=Dieter Rautenbach,Jens Vygen |title=A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing |journal=Journal of Discrete Algorithms |date=2007 |volume=7 |issue=4 |pages=377-390 |doi=10.1016/j.jda.2007.08.003}}</ref><ref>{{cite journal |author1=Ismail Rakip Karas,Sait Demir |title=Dijkstra algorithm interactive training software development for network analysis applications in GIS |journal=Energy Education Science and Technology Part A: Energy Science and Research |date=2011 |volume=28 |pages=445-452 |url=http://web.karabuk.edu.tr/ismail.karas/files/EEST_Part_A_2011_28(1)_445-452.pdf |author= |access-date=2020-03-04 |archive-url=https://web.archive.org/web/20200304070529/http://web.karabuk.edu.tr/ismail.karas/files/EEST_Part_A_2011_28(1)_445-452.pdf |archive-date=2020-03-04 |dead-url=no }}</ref><ref>{{cite journal |author1=Dean Djokic,David R. Maidment |title=Application of GIS Network Routines for Water Flow and Transport |journal=Journal of Water Resources Planning and Management |date=1993 |volume=119 |issue=2 |doi=10.1061/(ASCE)0733-9496(1993)119:2(229)}}</ref><ref>{{cite journal |author1=江琦浩 |title=迪杰斯特拉算法在企业成本控制研究中的应用 |journal=中国商贸}}</ref>。 |
||
如果有已知信息可用來估計某一點到目標點的距離,則可改用[[A*搜尋算法]],以減小最短路徑的搜索範圍,戴克斯特拉算法本身也可以看作是A*搜索算法的一个特例<ref name="geospatial">{{citation|title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools|first1=Michael John|last1=De Smith|first2=Michael F.|last2=Goodchild|first3=Paul|last3=Longley|publisher=Troubadour Publishing Ltd|year=2007|isbn=9781905886609|page=344|url=https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344|access-date=2020-03-04|archive-url=https://web.archive.org/web/20170227203644/https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344|archive-date=2017-02-27|dead-url=no}}.</ref><ref name="pythalgs">{{citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first=Magnus Lie|last=Hetland|publisher=Apress|year=2010|isbn=9781430232377|page=214|url=https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214|access-date=2020-03-04|archive-url=https://web.archive.org/web/20170228104339/https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214|archive-date=2017-02-28|dead-url=no}}.</ref>。 |
如果有已知信息可用來估計某一點到目標點的距離,則可改用[[A*搜尋算法]],以減小最短路徑的搜索範圍,戴克斯特拉算法本身也可以看作是A*搜索算法的一个特例<ref name="geospatial">{{citation|title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools|first1=Michael John|last1=De Smith|first2=Michael F.|last2=Goodchild|first3=Paul|last3=Longley|publisher=Troubadour Publishing Ltd|year=2007|isbn=9781905886609|page=344|url=https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344|access-date=2020-03-04|archive-url=https://web.archive.org/web/20170227203644/https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344|archive-date=2017-02-27|dead-url=no}}.</ref><ref name="pythalgs">{{citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first=Magnus Lie|last=Hetland|publisher=Apress|year=2010|isbn=9781430232377|page=214|url=https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214|access-date=2020-03-04|archive-url=https://web.archive.org/web/20170228104339/https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214|archive-date=2017-02-28|dead-url=no}}.</ref>。 |
||
戴克斯特拉算法本身采用了与[[Prim算法]]类似的[[贪心]]策略<ref name=Dijkstra1959 /><ref>{{citation|first=Robert Endre|last=Tarjan|authorlink=Robert Endre Tarjan|title=Data Structures and Network Algorithms|series=CBMS_NSF Regional Conference Series in Applied Mathematics|volume=44|year=1983|publisher=Society for Industrial and Applied Mathematics|page=75|quote=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.}}</ref><ref>{{cite journal|last1=Prim|first1=R.C.|title=Shortest connection networks and some generalizations|journal=Bell System Technical Journal|date=1957|volume=36|issue=6|pages=1389–1401|doi=10.1002/j.1538-7305.1957.tb01515.x|url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf|archiveurl=https://web.archive.org/web/20170718230207/http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf|archivedate=18 July 2017|access-date=18 July 2017|bibcode=1957BSTJ...36.1389P}}</ref><ref>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)</ref>。[[广度优先搜索]]可以看作是戴克斯特拉算法的一个特例<ref name=IntroToAlgo />。[[快速行进算法]]与戴克斯特拉算法同样有相似之处<ref>{{cite journal |author1=Danielsson, Per-Erik |coauthors=Lin, Qingfen |title=A Modified Fast Marching Method |journal=Image Analysis |date=24 June 2003 |pages=1154-1161 |url=https://link.springer.com/chapter/10.1007/3-540-45103-X_151}}</ref>。 |
|||
== 参考源程序 == |
== 参考源程序 == |
2020年3月25日 (三) 02:10的版本
戴克斯特拉算法 | |
---|---|
戴克斯特拉算法运行演示(找到A,B之间的最短路),本算法每次取出未访问结点中距离最小的,用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。 | |
概况 | |
類別 | 搜索算法[1][2] 贪心算法[1] 动态规划[3] |
資料結構 | 图(数据结构) 堆/优先队列(算法优化)[1][4] |
复杂度 | |
最坏时间复杂度 | (使用斐波那契堆优化的戴克斯特拉算法)[5][4] |
空間複雜度 | (使用链表存储边的情况)[1] |
相关变量的定义 | |
代表图中边数,代表图中结点个数,为目前所有实际最短路径值不确定结点的集合,为目前所有实际最短路径值确定结点的集合,为到某点的最短路径估计,为到某点的最短路径实际值。 |
图与树 搜索算法 |
---|
分类 |
相关主题 |
戴克斯特拉算法(英語:Dijkstra's algorithm),又译迪杰斯特拉算法,也作Dijkstra算法,是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表[6][7][8]。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图[8]的单源最短路径问题[9][1][2]。
该算法存在很多变体:戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径[8],后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径,产生一个最短路径树[1]。
该算法解决了圖 上带权的单源最短路径问题[1][10]:196–206。具体来说,戴克斯特拉算法设置了一顶点集合,在集合中所有的顶点与源点之间的最终最短路径权值均已确定[1]。算法反复选择最短路径估计最小的点并将加入中[1]。该算法常用于路由算法或者作为其他图算法的一个子模块[11]。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该演算法可以用来找到两个城市之间的最短路径[7][2]。
应当注意,绝大多数的戴克斯特拉算法不能有效处理带有负权边的图[1][12]。
戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索,并被认为是最良优先搜索的一个特例[9]。
算法描述
戴克斯特拉算法通過保留目前為止所找到的每個頂點從到的最短路徑來工作的[1][2]。初始時,原點的路径权重被賦為 0 (即原点的实际最短路径=0)[1][2]。同時把所有其他頂點的路徑長度設為無窮大,即表示我們不知道任何通向這些頂點的路徑[1]。當算法結束時, 中儲存的便是從到的最短路徑,或者如果路徑不存在的話是無窮大[1]。
松弛操作是戴克斯特拉算法的基礎操作:如果存在一條從到的邊,那麼從到的一条新路径是將邊添加到從到的路徑尾部來拓展一條從到的路径[1][8]。這條路徑的長度是[1]。如果這個值比目前已知的的值要小,那么可以用这个值來替代當前中的值[1]。松弛邊的操作一直執行到所有的都代表從到的最短路徑的长度值[1]。
算法維護兩個頂點集合和[1][8]。集合保留所有已知实际最短路径值的頂點,而集合則保留其他所有頂點[1][8]。集合初始狀態為空,而後每一步都有一個頂點從移動到[1][8]。這個被選擇的頂點是中擁有最小的值的頂點[1][2]。當一個頂點從中轉移到了中,算法對的每条外接邊進行松弛[1]。
《算法导论》中给出了以下伪代码[1]:该伪代码计算并保留图中原点到每一顶点的最短距离。其中,函数将頂點集合中有最小值的頂點从中删除并返回[1]。
1 function Dijkstra(G, w, s) 2 INITIALIZE-SINGLE-SOURCE(G, s) //实际上的操作是将每个除原点外的顶点的d[v]置为无穷大,d[s]=0 3 4 //Q是顶点V的一个优先队列,以顶点的最短路径估计排序 5 while() 6 do //选取u为Q中最短路径估计最小的顶点 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 i to n 4 5 6 7 while 8 begin 9 不属于S的D(u)最小的一个顶点 10 11 for 所有不属于S的顶点v 12 if then 13 end{=从a到z的最短路长度}
時間複雜度
我們可以用大O符號將该算法的運行時間表示為邊數和頂點數的函數[1]。
对于任何基于顶点集的实现,算法的运行时间是,其中和分别表示完成键的降序排列时间和从中提取最小键值的时间[1]。
对于没有任何优化的戴克斯特拉算法,实际上等价于每次遍历了整个图的所有结点来找到Q中满足条件的元素(即寻找最小的頂點是的),此外实际上还需要遍历所有的边一遍,因此算法的复杂度是[2]。
對於邊數少於的稀疏圖來說,我們可以用鄰接表來更有效的實現该算法[1]。
可以使用一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點(Extract-Min)以优化算法[13][14]。當用到二叉堆的時候,算法所需的時間為[13],斐波納契堆能提高一些性能,讓算法運行時間達到[4][14]。然而,使用斐波納契堆进行编程,有时会由于算法常数过大而导致速度没有显著提高[15]。
下面是一些戴克斯特拉算法经典实现的复杂度比较:
算法 | 时间复杂度 | 发现者(按照论文发表时间从前向后排序) |
---|---|---|
使用链表的戴克斯特拉算法 | 莱索雷克及格雷等人[16],艾兹赫尔·戴克斯特拉[8],明蒂[17],怀廷及希利尔[18] | |
使用二叉堆优化的戴克斯特拉算法 | 唐纳德·约翰逊[13] | |
使用斐波那契堆优化的戴克斯特拉算法 | 迈克尔·弗雷德曼及罗伯特·塔扬[4][14] | |
唐纳德·约翰逊[19],洛夫·卡尔松及帕特里西奥·波夫莱特[20] |
算法正确性证明
《算法导论》使用循环不变式(数学归纳法)给出了如下的一份证明[1]:
- 已知一带权图,其加权函数的值非负,源点为。对该图运行戴克斯特拉算法,对所有有。其中表示u点的最短路径估计,表示s到u点的最短路径。
- 证明:证明如下的循环不变式成立即可:在每次执行EXTRACT-MIN时,对每个顶点,有成立即可。由于上界性质,在加入了之后,一旦有,则在后面的每次循环中都不会改变这个性质。
- 初始化:第一次循环前,,因此循环不变式显然成立。
- 保持:实际上要证明每一轮循环中加入到中的结点满足。利用反证法,假设是第一个不满足此条件的结点,考虑循环开始前的状况,首先一定不等于,这是显然的。其次一定有到的路径,否则路径为无穷大。那么假设在进入时,有最短路径,假设该路径上存在两个点,。、,且x是y的前驱,路径可以分解为(此处表示经过这条路径,后同),其中路径和路径可以为空。由于是第一个不满足的,又因为是满足该条件的,而且一定已经被松弛过了,所以是满足该条件的。
- 现在只需要推出矛盾,即可证明u不存在:在之前出现,而且图中所有权值非负,因此有,所以:
,但是由于和同时在中,因此,因此必有,也就证明了点不可能不满足该条件,上述假设为假,原命题得证。 - 终止:终止时,,由于,因此,因此对所有有。
算法起源与历史
从鹿特丹到格罗宁根的最短路径是什么?实际上,这就是对于任意两座城市之间的最短路问题。解决这个问题实际上大概只花了我20分钟:一天早上,我和我的未婚妻在阿姆斯特丹购物,累了,我们便坐在咖啡馆的露台上喝咖啡,然后我就试了一下能否用一个算法解决最短路问题。正如我所说,这是一个20分钟的发现。不过实际上,我在3年后的1959年才把这个算法发表在论文上。即使现在来看这篇论文的可读性也非常高,这个算法之所以如此优雅,其中一个原因就是我没用笔纸就设计了它。后来我才知道,没用笔纸设计的优点之一是你不得不避免所有可避免的复杂问题。令我惊讶的是,这个算法最终成为我成名的基石之一。
——艾兹赫尔·戴克斯特拉在2001年的采访中提到戴克斯特拉算法的发现历程[7]
戴克斯特拉1956年在荷兰数学和计算机科学研究学会担任程序员时为了展示新型计算机ARMAC的功能曾思考过最短路径问题的解法[21]。他的目标是让不去实际计算的人也能理解这个问题和解决的方法,于是他在发现了这个算法之后在ARMAC上做了简单实验[7]。1959年,他正式将此算法发表在期刊上,该算法也成为了戴克斯特拉成名的基石之一[7][8]。
算法相关应用
链路状态路由协议中需要计算最短路时常常要用到该算法,開放最短路徑優先算法是该算法在網絡路由中的一個具體實現[11]。
戴克斯特拉算法及其改进算法本身应用广泛,尤其是在寻路、交通、规划中[22][23][24][25]。
如果有已知信息可用來估計某一點到目標點的距離,則可改用A*搜尋算法,以減小最短路徑的搜索範圍,戴克斯特拉算法本身也可以看作是A*搜索算法的一个特例[26][27]。
戴克斯特拉算法本身采用了与Prim算法类似的贪心策略[8][28][29][30]。广度优先搜索可以看作是戴克斯特拉算法的一个特例[1]。快速行进算法与戴克斯特拉算法同样有相似之处[31]。
参考源程序
以下是该算法不使用堆优化的一个C++实现[32]。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define edge pair < int, int>
#define infinite 32767
vector < pair < int, edge > > G;
vector<int> key, rel;
int N, E;
void init_keys()
{
key.resize(N);
key[0]=0;
for(int i=1; i<N; i++)
{
key[i]=infinite;
}
}
void dijkstra()
{
rel.resize(N);
int count=0;
sort(G.begin(), G.end());
while(count<E)
{
if((key[G[count].first]+G[count].second.second)<key[G[count].second.first])
{
rel[G[count].second.first]=G[count].first;
key[G[count].second.first]=key[G[count].first]+G[count].second.second;
}
count++;
};
}
int main()
{
int x, y, cost;
cin>>N>>E;
for(int i=0; i<E; i++)
{
cin>>x>>y>>cost;
G.push_back(pair <int, edge>(x-1, edge(y-1, cost)));
}
init_keys();
dijkstra();
cout<<"Shortest path: \n 1 is ROOT\n";
for(int i=1; i<N; i++)
{
cout<<"( "<<i+1<<", "<<rel[i]+1<<" )\n";
}
cout<<"Shortest path for? : ";
cin>>x;
cout<<"\nShortest path from 1 to "<<x<<" is "<<key[x-1];
return 0;
}
参见
參考
参考文献
- ^ 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 1.30 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年.
- ^ 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?
- ^ 7.0 7.1 7.2 7.3 7.4 Frana, Phil. An Interview with Edsger W. Dijkstra. Communications of the ACM. August 2010, 53 (8): 41–47. doi:10.1145/1787234.1787249.
- ^ 8.00 8.01 8.02 8.03 8.04 8.05 8.06 8.07 8.08 8.09 8.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).
- ^ 9.0 9.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. ISBN 978-3-540-77977-3. doi:10.1007/978-3-540-77978-0.
- ^ 11.0 11.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. doi:10.1109/ICC.2007.332.
- ^ 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.
- ^ 13.0 13.1 13.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.
- ^ 14.0 14.1 14.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).
- ^ 江琦浩. 迪杰斯特拉算法在企业成本控制研究中的应用. 中国商贸.
- ^ 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.
- ^ Layman806-zz. dijkstra.cpp. Github.
扩展阅读
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 24.3: Dijkstra's algorithm. 《算法导论》 第二版. 麻省理工学院出版社、标普全球. 2001: 595–601. ISBN 0-262-03293-7.
- Dial, Robert B. Algorithm 360: Shortest-path forest with topological ordering [H]. ACM通讯. 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
|