Dijkstra's algorithm

Dijkstra's algorithm is a method to find the shortest path from one node, or location, in a graph to all other nodes.^[1][2] In this process, it can find the shortest path from one node to another specific node. This can be used for navigation between points of interest like cities connected by roads^[3], or finding the shortest chain of mutual friends from two people on a social media platform.

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited node 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.

Requirements and Limitations

Dijkstra's algorithm works on a graph that has nodes and edges between those nodes. While the edges can have weight, representing a distance or cost, the algorithm also works on unweighted graphs by treating all edges as having a weight of 1.^[4]

The algorithm does not always find the shortest path on graphs with negative edge weights. Since the shortest path to a node is only determined once, potentially shorter paths from further away nodes with negative edge weights are not considered.

The algorithm also does not try to visit nodes that are closer to the destination node. It visits nodes in order of total distance from the starting point, similar to Breadth-first search. This leads to many more nodes than needed being potentially visited to find the shortest path.

Algorithm

Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a target node (upper right, green). Open nodes represent the set of "unvisited" nodes. Filled nodes are the visited ones, with color representing the distance: the redder, the closer (to the start node).

The algorithm requires a starting node to be provided, a queue to track new nodes, and a table that saves the total distance required to reach each node. The queue starts with only the starting node in it associated with a total distance of 0.

Until the destination node is reached, the algorithm repeats these steps:

• Take the node v with the shortest total distance out of the queue.
• Add all neighbors without a distance in the table to the queue with their distance from v.
• For each neighbor w, check the associated distance d of w. If d is greater than the distance from v to w :
  • Update d in the queue to be the distance from v to w.
  • Update w in the table to be this new distance.

After the algorithm completes, the total distance from the start to end node can be found in the distance table.

A specific path from the start to the destination node can be found by repeating the following steps until the start node is reached, beginning with v being the end node:

• Start with d being infinity
• Check all neighbors w of v :
  • If the total distance of w plus the distance from w to v is less than d, update d to that distance and set v to w.
  • Continue checking the rest of the neighbors of the original v.
• Add the current v to the shortest path from the start to end node.

Running time

The number of steps that Dijkstra's algorithm needs to complete on any graph is based on the number of nodes V and the number of edges E between those nodes. In the implementation of Dijkstra's algorithm using a queue, the worst-case number of steps required is ${\displaystyle O(|E|+|V|^{2})}$ (in Big O notation), or the number of edges |E| plus the number of nodes squared |V|² as:

• |E| : all edges must be considered as potentially being the shortest path from one node to another.
• |V|² : all nodes must check the distance between them and all of their neighbors when being evaluated. In the worst-case scenario, all nodes could be connected to all other nodes.

Related problems and algorithms

Bellman-Ford is a shortest path algorithm that allows edges to have negative weights, but requires more steps to run.

A* is a shortest path algorithm that can try to visit nodes going towards the end node first. This algorithm requires knowing the positions of the nodes instead of just their distances to each other, as well as computing a "priority" value for each neighbor in each step.

Pseudocode

In the pseudocode version of this algorithm's implementation^[5], the code u ← vertex in Q with min dist[u], searches for the vertex u in the vertex set Q that has the least dist[u] value. length(u, v) returns the length of the edge connecting the two neighbor-nodes u and v. The variable alt on line 18 is the length of the path from the root node to the neighbor node v if it were to go through u. If this path is shorter than the current shortest path recorded for v, that current path is replaced with this alt path. The prev array contains a pointer to the next node on the source graph to get the shortest route to the source.

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:            
 6          dist[v] ← INFINITY                 
 7          prev[v] ← UNDEFINED                
 8          add v to Q                     
 9      dist[source] ← 0                       
10     
11      while Q is not empty:
12          u ← vertex in Q with min dist[u]   
13                                             
14          remove u from Q
15         
16          for each neighbor v of u:           // only v that are still in Q
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:              
19                  dist[v] ← alt
20                  prev[v] ← u
21
22      return dist[], prev[]

If we only want the shortest path between vertices source and target, we can stop the search after line 15 if u = target (if the current node u is the target node). Now we can read the shortest path from source to target by going backwards:

1  S ← empty sequence
2  u ← target
3  if prev[u] is defined or u = source:          // Do something only if the vertex is reachable
4      while u is defined:                       // Construct the shortest path with a stack S
5          insert u at the beginning of S        // Push the vertex onto the stack
6          u ← prev[u]                           // Traverse from target to source

Now sequence S is the list of vertices that make up one of the shortest paths from source to target. If a path from source to target does not exist, sequence S will be empty.