Content deleted Content added
Citation bot (talk | contribs) Add: arxiv, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 111/467 |
→Dynamic programming perspective: downcase |
||
| (36 intermediate revisions by 28 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
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 39:
In the following [[pseudocode]], {{mono|dist}} is an array that contains the current distances from the {{mono|<var>source</var>}} to other vertices, i.e. {{mono|dist[<var>u</var>]}} is the current distance from the source to the vertex {{mono|<var>u</var>}}. The {{mono|prev}} array contains pointers to previous-hop nodes on the shortest path from source to the given vertex (equivalently, it is the ''next-hop'' on the path ''from'' the given vertex ''to'' the source). The code {{mono|u ← vertex in ''Q'' with min dist[u]}}, searches for the vertex {{mono|<var>u</var>}} in the vertex set {{mono|<var>Q</var>}} that has the least {{mono|dist[<var>u</var>]}} value. {{mono|Graph.Edges(<var>u</var>, <var>v</var>)}} returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes {{mono|<var>u</var>}} and {{mono|<var>v</var>}}. The variable {{mono|<var>alt</var>}} on line 14 is the length of the path from the {{mono|<var>source</var>}} node to the neighbor node {{mono|<var>v</var>}} if it were to go through {{mono|<var>u</var>}}. If this path is shorter than the current shortest path recorded for {{mono|<var>v</var>}}, then the distance of {{mono|<var>v</var>}} is updated to {{mono|<var>alt</var>}}.<ref name=" mehlhorn" />
[[File:DijkstraDemo.gif|thumb|A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting ''u'' and prev[''u'']. Blue lines indicate where relaxing happens, i.e., connecting ''v'' with a node ''u'' in ''Q'', which gives a shorter path from the source to ''v''.]]
1 '''function''' Dijkstra(''Graph'', ''source''):
2
3 '''for each''' vertex ''v'' in ''Graph.Vertices'': 4 dist[''v''] ← INFINITY
5 prev[''v''] ← UNDEFINED
6 add ''v'' to ''Q''
7 dist[''source''] ← 0
8
9 '''while''' ''Q'' is not empty:
10 ''u'' ← vertex in ''Q'' with minimum dist[u]
11
12
13 '''for each'''
14 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
15 '''if''' ''alt'' < dist[''v'']:
16 dist[''v''] ← ''alt''
17 prev[''v''] ← ''u''
18
▲ 20 '''return''' dist[], prev[]
To find the shortest path between vertices {{mono|<var>source</var>}} and {{mono|<var>target</var>}}, the search terminates after line 10 if {{mono|<var>u</var> {{=}} <var>target</var>}}. The shortest path from {{mono|<var>source</var>}} to {{mono|<var>target</var>}} can be obtained by reverse iteration:
2 ''u'' ← ''target''
3 '''if''' prev[''u''] is defined '''or''' ''u'' = ''source'': ''// 4 '''while''' ''u'' is defined: ''// Construct the shortest path with a stack S''
5
6 ''u'' ← prev[''u''] ''// Traverse from target to source''
Now sequence {{mono|<var>S</var>}} is the list of vertices constituting one of the shortest paths from {{mono|<var>source</var>}} to {{mono|<var>target</var>}}, or the empty sequence if no path exists.
Line 72 ⟶ 75:
===Using a priority queue===
A min-priority queue is an abstract data type that provides 3 basic operations: {{mono|add_with_priority()}}, {{mono|decrease_priority()}} and {{mono|extract_min()}}. As mentioned earlier, using such a data structure can lead to faster computing times than using a basic queue. Notably, [[Fibonacci heap]]{{sfn|Fredman|Tarjan|1984}} or [[Brodal queue]] offer optimal implementations for those 3 operations. As the algorithm is slightly different in appearance, it is mentioned here, in pseudocode as well:
1 '''function''' Dijkstra(''Graph'', ''source''):
2 Q ← Queue storing vertex priority
3
4 dist[''source''] ← 0 ''// Initialization''
5 ''Q''.add_with_priority(''source'', 0) ''// associated priority equals dist[·]''
6
7 '''for each''' vertex ''v'' in ''Graph.Vertices'':
8 '''if''' ''v'' ≠ ''source''
9 prev[''v''] ← UNDEFINED ''// Predecessor of v''
10 dist[''v''] ← INFINITY ''// Unknown distance from source to v''
11 Q.add_with_priority(v, INFINITY)
12
13
14 '''while''' ''Q'' is not empty: ''// The main loop''
15 ''u'' ← ''Q''.extract_min() ''// Remove and return best vertex''
16 '''for each'''
17 ''alt'' ← dist[''u''] + Graph.Edges(''u'', ''v'')
18 '''if''' ''alt'' < dist[''v'']:
19 prev[''v''] ← ''u''
20 dist[''v''] ← ''alt''
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 126 ⟶ 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 151 ⟶ 156:
Moreover, not inserting all nodes in a graph makes it possible to extend the algorithm to find the shortest path from a single source to the closest of a set of target nodes on infinite graphs or those too large to represent in memory. The resulting algorithm is called ''uniform-cost search'' (UCS) in the artificial intelligence literature{{r|felner}}<ref name="aima">{{Cite AIMA|3|pages=75, 81}}</ref><ref>Sometimes also ''least-cost-first search'': {{cite journal |last=Nau |first=Dana S. |year=1983 |title=Expert computer systems |url=https://www.cs.umd.edu/~nau/papers/nau1983expert.pdf |journal=Computer |publisher=IEEE |volume=16 |issue=2 |pages=63–85 |doi=10.1109/mc.1983.1654302 |s2cid=7301753}}</ref> and can be expressed in pseudocode as<!--NOTE TO EDITORS: Don't get confused by "uniform" in the name and remove costs from the pseudocode. UCS includes costs and is different from breadth-first search.-->
'''procedure''' uniform_cost_search(start) '''is'''
node ← start
frontier ← priority queue containing node only
expanded ← empty set
'''do'''
'''if''' frontier is empty '''then'''
'''return''' failure
node ← frontier.pop()
'''if''' node is a goal state '''then'''
'''return''' solution(node)
expanded.add(node)
'''for each''' of node's neighbors ''n'' '''do'''
'''if''' ''n'' is not in expanded and not in frontier '''then'''
frontier.add(''n'')
'''else if''' ''n'' is in frontier with higher cost
replace existing node with ''n''
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 ===
As well as simply computing distances and paths, Dijkstra's algorithm can be used to sort vertices by their distances from a given starting vertex.
In 2023, Haeupler, Rozhoň, Tětek, Hladík, and [[Robert Tarjan|Tarjan]] (one of the inventors of the 1984 heap), proved that, for this sorting problem on a positively-weighted directed graph, a version of Dijkstra's algorithm with a special heap data structure has a runtime and number of comparisons that is within a constant factor of optimal among [[Comparison sort|comparison-based]] algorithms for the same sorting problem on the same graph and starting vertex but with variable edge weights. To achieve this, they use a comparison-based heap whose cost of returning/removing the minimum element from the heap is logarithmic in the number of elements inserted after it rather than in the number of elements in the heap.<ref>{{
===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 196 ⟶ 202:
In fact, Dijkstra's explanation of the logic behind the algorithm:{{sfn|Dijkstra|1959|p=270}}
{{blockquote|'''Problem 2.''' Find the path of minimum total length between two given nodes
We use the fact that, if
is a paraphrasing of [[Richard Bellman|Bellman's]] [[Bellman equation#Bellman's principle of optimality|
== See also ==
Line 239 ⟶ 245:
[[Category:Graph algorithms]]
[[Category:Search algorithms]]
[[Category:Greedy algorithms]]
[[Category:Routing algorithms]]
[[Category:Combinatorial optimization]]
| |||