Content deleted Content added
m →Pseudocode: Minor changes and formatting to pseudocode |
m Move value of deprecated Template:Rp parameter to a new one |
||
Line 5:
'''Dijkstra's algorithm''' ({{IPAc-en|ˈ|d|aɪ|k|s|t|r|ə|z}} {{respell|DYKE|strəz}}) is an [[algorithm]] for finding the [[Shortest path problem|shortest paths]] between [[Vertex (graph theory)|nodes]] in a weighted [[Graph (abstract data type)|graph]], which may represent, for example, a [[road network]]. It was conceived by [[computer scientist]] [[Edsger W. Dijkstra]] in 1956 and published three years later.<ref>{{cite web |last=Richards |first=Hamilton |title=Edsger Wybe Dijkstra |url=http://amturing.acm.org/award_winners/dijkstra_1053701.cfm |access-date=16 October 2017 |website=A.M. Turing Award |publisher=Association for Computing Machinery |quote=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?}}</ref><ref name="Dijkstra Interview2">{{cite journal |last=Frana |first=Phil |date=August 2010 |title=An Interview with Edsger W. Dijkstra |journal=Communications of the ACM |volume=53 |issue=8 |pages=41–47 |doi=10.1145/1787234.1787249 |s2cid=27009702 |doi-access=}}</ref><ref name="Dijkstra19592">{{cite journal |last1=Dijkstra |first1=E. W. |author-link=Edsger W. Dijkstra |year=1959 |title=A note on two problems in connexion with graphs |url=https://ir.cwi.nl/pub/9256/9256D.pdf |journal=Numerische Mathematik |volume=1 |pages=269–271 |citeseerx=10.1.1.165.7577 |doi=10.1007/BF01386390 |s2cid=123284777}}</ref>
Dijkstra's algorithm finds the shortest path from a given source node to every other node.<ref name="mehlhorn">{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn |title=Algorithms and Data Structures: The Basic Toolbox |last2=Sanders |first2=Peter |author2-link=Peter Sanders (computer scientist) |publisher=Springer |year=2008 |isbn=978-3-540-77977-3 |chapter=Chapter 10. Shortest Paths |doi=10.1007/978-3-540-77978-0 |chapter-url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ShortestPaths.pdf}}</ref>{{rp|pages=196–206}} It can be used to find the shortest path to a specific destination node, by terminating the algorithm after determining the shortest path to the destination node. For example, if the nodes of the graph represent cities, and the costs of edges represent the distances between pairs of cities connected by a direct road, then Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A common application of shortest path algorithms is network [[routing protocol]]s, most notably [[IS-IS]] (Intermediate System to Intermediate System) and [[Open Shortest Path First|OSPF]] (Open Shortest Path First). It is also employed as a [[subroutine]] in algorithms such as [[Johnson's algorithm]].
The algorithm uses a [[Priority queue#Min-priority queue|min-priority queue]] data structure for selecting the shortest paths known so far. Before more advanced priority queue structures were discovered, Dijkstra's original algorithm ran in <math>\Theta(|V|^2)</math> [[Time complexity|time]], where <math>|V|</math> is the number of nodes.<ref>{{Cite book |last=Schrijver |first=Alexander |title=Optimization Stories |chapter=On the history of the shortest path problem |date=2012 |chapter-url=http://ftp.gwdg.de/pub/misc/EMIS/journals/DMJDMV/vol-ismp/32_schrijver-alexander-sp.pdf |series=Documenta Mathematica Series |volume=6 |pages=155–167 |doi=10.4171/dms/6/19 |doi-access=free |isbn=978-3-936609-58-5}}</ref>{{sfn|Leyzorek|Gray|Johnson|Ladew|1957}} {{harvnb|Fredman|Tarjan|1984}} proposed a [[Fibonacci heap]] priority queue to optimize the running time complexity to <math>\Theta(|E|+|V|\log|V|)</math>. This is [[Asymptotic computational complexity|asymptotically]] the fastest known single-source [[Shortest path problem|shortest-path algorithm]] for arbitrary [[directed graph]]s with unbounded non-negative weights. However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can be [[Dijkstra's algorithm#Specialized variants|improved further]]. If preprocessing is allowed, algorithms such as [[Contraction hierarchy|contraction hierarchies]] can be up to seven orders of magnitude faster.
| |||