Dijkstra's algorithm

Dijkstra's algorithm ( , ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 12 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Dijkstra's algorithm ( , ) is an algorithm for finding the shortest paths between nodes in a weighted 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. Dijkstra's algorithm finds the shortest path from a given source node to every other node.

It can be used to find the shortest path to a specific destination node, by terminating the algorithm after determining the shortest path to that 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 protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). It is also employed as a subroutine in algorithms such as Johnson's algorithm. 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 \Theta(|V|^2) time, where |V| is the number of nodes.…

Dijkstra's algorithm ( , ) is an algorithm for finding the shortest paths between nodes in a weighted 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. Dijkstra's algorithm finds the shortest path from a given source node to every other node.

It can be used to find the shortest path to a specific destination node, by terminating the algorithm after determining the shortest path to that 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 protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). It is also employed as a subroutine in algorithms such as Johnson's algorithm. 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 \Theta(|V|^2) time, where |V| is the number of nodes. proposed a Fibonacci heap priority queue to optimize the running time complexity to \Theta(|E|+|V|\log|V|) , where |E| is the number of edges. This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can be improved further. If preprocessing is allowed, algorithms such as 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, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing. In many fields, particularly artificial intelligence, Dijkstra's algorithm or a variant offers a uniform cost search and is formulated as an instance of the more general idea of best-first search.

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 step 3. Once the loop exits (steps 3–5), every visited node contains its shortest distance from the starting node.

Pseudocode

In the following pseudocode, is an array that contains the current distances from the to other vertices, i.e. is the current distance from the source to the vertex . The 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 , searches for the vertex in the vertex set that has the least value. returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes and . The variable on line 14 is the length of the path from the node to the neighbor node if it were to go through .

If this path is shorter than the current shortest path recorded for , then the distance of is updated to . [[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 Q.remove(u) 12 13 for each edge (u, v) in Graph: 14 alt ← dist[u] + Graph.Distance(u,v) 15 if alt if alt block, the becomes an operation. Yet another alternative is to add nodes unconditionally to the priority queue and to instead check after extraction ( u ← Q.extract_min() ) that it isn't revisiting, or that no shorter connection was found yet in the if alt block.

This can be done by additionally extracting the associated priority p from the queue and only processing further if p == dist[u] inside the while Q is not empty loop. 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. The simplest version of Dijkstra's algorithm stores the vertex set as a linked list or array, and edges as an adjacency list or matrix. In this case, extract-minimum is simply a linear search through all vertices in , so the running time is \Theta(|E| + |V|^2) = \Theta(|V|^2) .

For sparse graphs, that is, graphs with far fewer than |V|^2 edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, Fibonacci heap or a priority heap as a priority queue to implement extracting minimum efficiently. To perform decrease-key steps in a binary heap efficiently, it is necessary to use an auxiliary data structure that maps each vertex to its position in the heap, and to update this structure as the priority queue changes.

With a self-balancing binary search tree or binary heap, the algorithm requires \Theta((|E| + |V|) \log |V|) time in the worst case; for connected graphs this time bound can be simplified to \Theta( | E | \log | V | ) . The Fibonacci heap improves this to \Theta(|E| + |V| \log|V|) .

When using binary heaps, the average case time complexity is lower than the worst-case: assuming edge costs are drawn independently from a common probability distribution, the expected number of decrease-key operations is bounded by \Theta(|V| \log (|E|/|V|)) , giving a total running time of

Practical optimizations and infinite graphs

In common presentations of Dijkstra's algorithm, initially all nodes are entered into the priority queue. This is, however, not necessary: the algorithm can start with a priority queue that contains only one item, and insert new items as they are discovered (instead of doing a decrease-key, check whether the key is in the queue; if it is, decrease its key, otherwise insert it).

This variant has the same worst-case bounds as the common variant, but maintains a smaller priority queue in practice, speeding up queue operations. 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 and can be expressed in pseudocode as 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 is the length of the shortest path from the start node to any node satisfying the "goal" predicate, each edge has cost at least , and the number of neighbors per node is bounded by , then the algorithm's worst-case time and space complexity are both in . Further optimizations for the single-target case include bidirectional variants, goal-directed variants such as the A* algorithm (see ), 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 routing to connecting and to their respective "transit nodes" followed by shortest-path computation between these transit nodes using a "highway".

Combinations of such techniques may be needed for optimal practical performance on specific problems.

Practical performance considerations

Although Dijkstra's algorithm is optimal for graphs with non-negative edge weights, its practical runtime depends on both data structures and graph properties. Using a binary heap results in a running time of O((V+E)logV). Alternatives such as Fibonacci heaps provide better theoretical bounds but often perform worse in real applications because of large constant factors.

Graph structure also plays a major role. Sparse networks, such as road maps, allow Dijkstra's algorithm to operate efficiently since most vertices have low degree. Dense graphs increase relaxations and slow down the process.

Because of this, modern routing systems often use Dijkstra's algorithm together with preprocessing methods such as A* search, landmark heuristics, or contraction hierarchies, which significantly reduce the search space. Memory locality is another important factor. Cache-optimized priority queues and adjacency layouts can reduce latency for large graphs that exceed CPU cache limitations.

Because of these considerations, most real-world systems use specialized Dijkstra variants tuned for specific graph families and hardware constraints.

Specialized variants

When arc weights are small integers (bounded by a parameter C ), specialized queues can be used for increased speed. The first algorithm of this type was Dial's algorithm for graphs with positive integer edge weights, which uses a bucket queue to obtain a running time The use of a van Emde Boas tree as the priority queue brings the complexity to Another interesting variant based on a combination of a new radix heap and the well-known Fibonacci heap runs in time Finally, the best algorithms in this special case run in O(|E|\log\log|V|) time and O(|E| + |V|\min\{(\log|V|)^{1/3+\varepsilon}, (\log C)^{1/4+\varepsilon}\}) time.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378301409 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

17 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.