Content deleted Content added
Tag: Reverted |
→Dynamic programming perspective: downcase |
||
| (29 intermediate revisions by 25 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
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
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
The algorithm requires a starting node, and
# Create a [[Set (abstract data type)|set]] of all unvisited nodes: the unvisited set.
Line 25:
# From the unvisited set, select the current node to be the one with the smallest (finite) distance; initially, this is the starting node (distance zero). If the unvisited set is empty, or contains only nodes with infinite distance (which are unreachable), then the algorithm terminates by skipping to step 6. If the only concern is the path to a target node, the algorithm terminates once the current node is the target node. Otherwise, the algorithm continues.
# For the current node, consider all of its unvisited neighbors and update their distances through the current node; compare the newly calculated distance to the one currently assigned to the neighbor and assign the smaller one to it. For example, if the current node ''A'' is marked with a distance of 6, and the edge connecting it with its neighbor ''B'' has length 2, then the distance to ''B'' through ''A'' is 6 + 2 = 8. If B was previously marked with a distance greater than 8, then update it to 8 (the path to B through A is shorter). Otherwise, keep its current distance (the path to B through A is not the shortest).
# After considering all of the current node's unvisited neighbors, the current node is removed from the unvisited set. Thus a visited node is never rechecked, which is correct because the distance recorded on the current node is minimal (as ensured in step 3), and thus final. Repeat from
# Once the loop exits (steps 3–5), every visited node contains its shortest distance from the starting node.
Line 50:
9 '''while''' ''Q'' is not empty:
10 ''u'' ← vertex in ''Q'' with minimum dist[u]
11 Q.remove
12
13 '''for each'''
14 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
15 '''if''' ''alt'' < dist[''v'']:
Line 66:
3 '''if''' prev[''u''] is defined '''or''' ''u'' = ''source'': ''// Proceed if the vertex is reachable''
4 '''while''' ''u'' is defined: ''// Construct the shortest path with a stack S''
5
6 ''u'' ← prev[''u''] ''// Traverse from target to source''
Line 77:
1 '''function''' Dijkstra(''Graph'', ''source''):
2
3
4 dist[''source''] ← 0 ''// Initialization''
5 ''Q''.add_with_priority(''source'', 0) ''// associated priority equals dist[·]''
Line 89:
12
13
14 '''while''' ''Q'' is not empty:
15 ''u'' ← ''Q''.extract_min()
16 '''for each'''
17 ''alt'' ← dist[''
18 '''if''' ''alt'' < dist[''v'']:
19 prev[''v''] ← ''u''
Line 98:
21 ''Q''.decrease_priority(''v'', ''alt'')
22
23 '''return''' (dist, prev)
Instead of filling the priority queue with all nodes in the initialization phase, it is possible to initialize it to contain only ''source''; then, inside the <code>'''if''' ''alt'' < dist[''v'']</code> block, the {{mono|decrease_priority()}} becomes an {{mono|add_with_priority()}} operation.<ref name=" mehlhorn" />{{rp|198}}
Line 104:
Yet another alternative is to add nodes unconditionally to the priority queue and to instead check after extraction (<code>''u'' ← ''Q''.extract_min()</code>) that it isn't revisiting, or that no shorter connection was found yet in the <code>if alt < dist[v]</code> block. This can be done by additionally extracting the associated priority <code>''p''</code> from the queue and only processing further <code>'''if''' ''p'' == dist[''u'']</code> inside the <code>'''while''' ''Q'' is not empty</code> loop.<ref name="Note2">Observe that {{mono|''p'' < dist[''u'']}} cannot ever hold because of the update {{mono|dist[''v''] ← ''alt''}} when updating the queue. See https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key for discussion.</ref>
These alternatives can use entirely array-based priority queues without decrease-key functionality, which have been found to achieve even faster computing times in practice. However, the difference in performance was found to be narrower for denser graphs.<ref name="chen_072">{{cite book |last1=Chen |first1=M. |url=http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf |title=Priority Queues and Dijkstra's Algorithm – UTCS Technical Report TR-07-54 – 12 October 2007 |last2=Chowdhury |first2=R. A. |last3=Ramachandran |first3=V. |last4=Roche |first4=D. L. |last5=Tong |first5=L. |publisher=The University of Texas at Austin, Department of Computer Sciences |year=2007 |___location=Austin, Texas |ref=
== Proof ==
Line 131:
Bounds of the running time of Dijkstra's algorithm on a graph with edges ''{{mvar|E}}'' and vertices ''{{mvar|V}}'' can be expressed as a function of the number of edges, denoted <math>|E|</math>, and the number of vertices, denoted <math>|V|</math>, using [[big-O notation]]. The complexity bound depends mainly on the data structure used to represent the set ''{{mvar|Q}}''. In the following, upper bounds can be simplified because <math>|E|</math> is <math>O(|V|^2)</math> for any simple graph, but that simplification disregards the fact that in some problems, other upper bounds on <math>|E|</math> may hold.
For any data structure for the vertex set ''{{mvar|Q}}'', the running time
: <math>\Theta(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em}),</math>
Line 174:
Its complexity can be expressed in an alternative way for very large graphs: when {{math|''C''<sup>*</sup>}} is the length of the shortest path from the start node to any node satisfying the "goal" predicate, each edge has cost at least ''{{mvar|ε}}'', and the number of neighbors per node is bounded by ''{{mvar|b}}'', then the algorithm's worst-case time and space complexity are both in {{math|''O''(''b''<sup>1+⌊''C''<sup>*</sup> {{frac}} ''ε''⌋</sup>)}}.{{r|aima}}
Further optimizations for the single-target case include [[Bidirectional search|bidirectional]] variants, goal-directed variants such as the [[A* algorithm]] (see {{slink||Related problems and algorithms}}), graph pruning to determine which nodes are likely to form the middle segment of shortest paths (reach-based routing), and hierarchical decompositions of the input graph that reduce {{math|''s''–''t''}} routing to connecting ''{{mvar|s}}'' and ''{{mvar|t}}'' to their respective "[[Transit Node Routing|transit nodes]]" followed by shortest-path computation between these transit nodes using a "highway".<ref name="speedup2">{{cite conference |last1=Wagner |first1=Dorothea |last2=Willhalm |first2=Thomas |year=2007 |title=Speed-up techniques for shortest-path computations |conference=STACS |pages=23–36}}</ref> Combinations of such techniques may be needed for optimal practical performance on specific problems.<ref>{{cite journal |last1=Bauer |first1=Reinhard |last2=Delling |first2=Daniel |last3=Sanders |first3=Peter |last4=Schieferdecker |first4=Dennis |last5=Schultes |first5=Dominik |last6=Wagner |first6=Dorothea |year=2010 |title=Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm |url=https://publikationen.bibliothek.kit.edu/1000014952 |journal=
=== Optimality for comparison-sorting by distance ===
Line 181:
===Specialized variants===
When arc weights are small integers (bounded by a parameter <math>C</math>), specialized queues can be used for increased speed. The first algorithm of this type was Dial's algorithm{{Sfn|Dial|1969}} for graphs with positive integer edge weights, which uses a [[bucket queue]] to obtain a running time <math>O(|E|+|V|C)</math>. The use of a [[Van Emde Boas tree]] as the priority queue brings the complexity to <math>O(|E|+|V|\log C/\log\log |V|C)</math> .{{sfn|Ahuja|Mehlhorn|Orlin|Tarjan|1990}} Another interesting variant based on a combination of a new [[radix heap]] and the well-known Fibonacci heap runs in time <math>O(|E|+|V|\sqrt{\log C})</math> .{{sfn|Ahuja|Mehlhorn|Orlin|Tarjan|1990}} Finally, the best algorithms in this special case run in <math>O(|E|\log\log|V|)</math>{{sfn|Thorup|2000}} time and <math>O(|E| + |V|\min\{(\log|V|)^{1/3+\varepsilon}, (\log C)^{1/4+\varepsilon}\})</math> time.{{sfn|Raman|1997}}
== Related problems and algorithms ==
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|
== See also ==
Line 245:
[[Category:Graph algorithms]]
[[Category:Search algorithms]]
[[Category:Greedy algorithms]]
[[Category:Routing algorithms]]
[[Category:Combinatorial optimization]]
| |||