Content deleted Content added
→Optimality for comparison-sorting by distance: and starting vertex |
→Dynamic programming perspective: downcase |
||
| (43 intermediate revisions by 33 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 15:
== History ==
{{blockquote|What is the shortest way to travel from [[Rotterdam]] to [[Groningen]], in general: from given city to given city. [[Shortest path problem|It is the algorithm for the shortest path]], which I designed in about twenty minutes. One morning I was shopping in [[Amsterdam]] with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.|Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001<ref name="Dijkstra Interview2"/>}}
Dijkstra thought about the shortest path problem while working as a programmer at the [[Centrum Wiskunde & Informatica|Mathematical Center in Amsterdam]] in 1956. He wanted to demonstrate the capabilities of
== 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
19 '''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 71 ⟶ 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 108 ⟶ 114:
The base case is when there is just one visited node, {{mono|source}}. Its distance is defined to be zero, which is the shortest distance, since negative weights are not allowed. Hence, the hypothesis holds.
===
Assuming that the hypothesis holds for <math>k</math> visited nodes, to show it holds for <math>k+1</math> nodes, let {{mono|u}} be the next visited node, i.e. the node with minimum {{code|dist[u]}}. The claim is that {{code|dist[u]}} is the shortest distance from {{mono|source}} to {{mono|u}}.
Line 114 ⟶ 120:
* In the former case, let {{mono|w}} be the first unvisited node on this shorter path. By induction, the shortest paths from {{mono|source}} to {{mono|u}} and {{mono|w}} through visited nodes only have costs {{code|dist[u]}} and {{code|dist[w]}} respectively. This means the cost of going from {{mono|source}} to {{mono|u}} via {{mono|w}} has the cost of at least {{code|dist[w]}} + the minimal cost of going from {{mono|w}} to {{mono|u}}. As the edge costs are positive, the minimal cost of going from {{mono|w}} to {{mono|u}} is a positive number. However, {{code|dist[u]}} is at most {{code|dist[w]}} because otherwise w would have been picked by the priority queue instead of u. This is a contradiction, since it has already been established that {{code|dist[w]}} + a positive number < {{code|dist[u]}}.
* In the latter case, let {{mono|w}} be the last but one node on the shortest path. That means {{code|dist[w] + Graph.Edges[w,u] < dist[u]}}. That is a contradiction because by the time {{mono|w}} is visited, it should have set {{code|dist[u]}} to at most {{code|dist[w] + Graph.Edges[w,u]}}.
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 134 ⟶ 139:
The simplest version of Dijkstra's algorithm stores the vertex set ''{{mvar|Q}}'' as a linked list or array, and edges as an [[adjacency list]] or [[Adjacency matrix|matrix]]. In this case, extract-minimum is simply a linear search through all vertices in ''{{mvar|Q}}'', so the running time is <math>\Theta(|E| + |V|^2) = \Theta(|V|^2)</math>.
For [[
: <math>\Theta((|E| + |V|) \log |V|)</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|
== Related problems and algorithms ==
Dijkstra's original algorithm can be extended with modifications. For example, sometimes it is desirable to present solutions which are less than mathematically optimal. To obtain a ranked list of less-than-optimal solutions, the optimal solution is first calculated. A single edge appearing in the optimal solution is removed from the graph, and the optimum solution to this new graph is calculated. Each edge of the original solution is suppressed in turn and a new shortest-path calculated. The secondary solutions are then ranked and presented after the first optimal solution.
Dijkstra's algorithm is usually the working principle behind [[
Unlike Dijkstra's algorithm, the [[Bellman–Ford algorithm]] can be used on graphs with negative edge weights, as long as the graph contains no [[negative cycle]] reachable from the source vertex ''s''. The presence of such cycles means that no shortest path can be found, since the label becomes lower each time the cycle is traversed. (This statement assumes that a "path" is allowed to repeat vertices. In [[graph theory]] that is normally not allowed. In [[theoretical computer science]] it often is allowed.) It is possible to adapt Dijkstra's algorithm to handle negative weights by combining it with the Bellman-Ford algorithm (to remove negative edges and detect negative cycles): [[Johnson's algorithm]].
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 234 ⟶ 240:
* [http://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html Implementation of Dijkstra's algorithm using TDD], [[Robert Cecil Martin]], The Clean Code Blog
{{Edsger Dijkstra}}{{Graph traversal algorithms}}{{Optimization algorithms|combinatorial|state=autocollapse}}
[[Category:Edsger W. Dijkstra|Algorithm]]
[[Category:1959 in computing]]
[[Category:Graph algorithms]]
[[Category:Search algorithms]]
[[Category:Greedy algorithms]]
[[Category:Routing algorithms]]
[[Category:Combinatorial optimization]]
| |||