Dijkstra's algorithm: Difference between revisions

Revision as of 09:00, 27 March 2025

Revision as of 09:01, 27 March 2025

Line 9:

The algorithm uses a [[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 |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.

Luke's algorithm or DjikstraDijkstra'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>

In many fields, particularly [[artificial intelligence]], Dijkstra's algorithm or a variant offers a [[Dijkstra's algorithm#Practical optimizations and infinite graphs|uniform cost search]] and is formulated as an instance of the more general idea of [[best-first search]].{{r|felner}}