Dijkstra's algorithm: Difference between revisions

Revision as of 15:08, 28 June 2025

Latest revision as of 18:47, 18 August 2025

(5 intermediate revisions by 5 users not shown)

Line 3:

{{Use dmy dates|date=December 2019}}

{{Infobox algorithm|class=[[Search algorithm]]<br>[[Greedy algorithm]]<br>[[Dynamic programming]]<ref>Controversial, see {{cite journal|author1=Moshe Sniedovich|title=Dijkstra's algorithm revisited: the dynamic programming connexion|journal=Control and Cybernetics|date=2006|volume=35|pages=599–620|url=https://www.infona.pl/resource/bwmeta1.element.baztech-article-BAT5-0013-0005/tab/summary}} and [[#Dynamic programming perspective|below part]].</ref>|image=Dijkstra Animation.gif|caption=Dijkstra's algorithm to find the shortest path between ''a'' and ''b''. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.|data=[[Graph (data structure)|Graph]]<br>Usually used with [[priority queue]] or [[Heap (data structure)|heap]] for optimization{{sfn|Cormen|Leiserson|Rivest|Stein|2001}}{{sfn|Fredman|Tarjan|1987}}|time=<math>\Theta(|E| + |V| \log|V|)</math>{{sfn|Fredman|Tarjan|1987}}|best-time=|average-time=|space=|optimal=|complete=}}

'''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.

Dijkstra's algorithm is commonly used on graphs where the edge weights are positive integers or real numbers. It can be generalized to any graph where the edge weights are [[Partially ordered set|partially ordered]], provided the subsequent labels (a subsequent label is produced when traversing an edge) are [[Monotonic function|monotonically]] non-decreasing.<ref name="Generic Dijkstra2">{{cite journal |last1=Szcześniak |first1=Ireneusz |last2=Jajszczyk |first2=Andrzej |last3=Woźna-Szcześniak |first3=Bożena |year=2019 |title=Generic Dijkstra for optical networks |journal=Journal of Optical Communications and Networking |volume=11 |issue=11 |pages=568–577 |arxiv=1810.04481 |doi=10.1364/JOCN.11.000568 |s2cid=52958911}}</ref><ref name="Generic Dijkstra correctness2">{{citation |last1=Szcześniak |first1=Ireneusz |title=NOMS 2023-2023 IEEE/IFIP Network Operations and Management Symposium |pages=1–7 |year=2023 |chapter=Generic Dijkstra: Correctness and tractability |arxiv=2204.13547 |doi=10.1109/NOMS56928.2023.10154322 |isbn=978-1-6654-7716-1 |s2cid=248427020 |last2=Woźna-Szcześniak |first2=Bożena}}</ref>

Line 18:

== Algorithm ==

[[File:Dijkstras_progress_animation.gif|thumb|Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a target node (upper right, green) in a [[Robotics|robot]] [[motion planning]] problem. Open nodes represent the "tentative" set (aka set of "unvisited" nodes). Filled nodes are the visited ones, with color representing the distance: the redder, the closer (to the start node). Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular [[wavefront]] as Dijkstra's algorithm does not useuses a [[Consistent heuristic|heuristic]] of picking the shortest known path so far.]]

The algorithm requires a starting node, and computes the shortest distance from that starting node to each other node. Dijkstra's algorithm starts with infinite distances and tries to improve them step by step:

Line 205:

We use the fact that, if {{mvar|R}} is a node on the minimal path from {{mvar|P}} to {{mvar|Q}}, knowledge of the latter implies the knowledge of the minimal path from {{mvar|P}} to {{mvar|R}}.}}

is a paraphrasing of [[Richard Bellman|Bellman's]] [[Bellman equation#Bellman's principle of optimality|Principleprinciple of Optimalityoptimality]] in the context of the shortest path problem.

== See also ==