Dijkstra's algorithm: Difference between revisions

Revision as of 17:09, 18 July 2025

Latest revision as of 18:47, 18 August 2025

(2 intermediate revisions by 2 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]].

Line 49:

8

9 '''while''' ''Q'' is not empty:

10 ''u'' ← vertex in ''Q'' with minimum dist[vu]

11 Q.remove(u)

12

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 ==