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. 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, or finding the shortest chain of mutual friends from two people on a social media platform.

## 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.

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

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  (in Big O notation), or the number of edges |_E_| plus the number of nodes squared |_V_|<sup>2</sup> as:

- |_E|_ : all edges must be considered as potentially being the shortest path from one node to another.
- |_V_|<sup>2</sup> : 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, the code , searches for the vertex  in the vertex set  that has the least  value.  returns the length of the edge connecting the two neighbor-nodes  and . The variable  on line 18 is the length of the path from the root node to the neighbor node  if it were to go through . If this path is shorter than the current shortest path recorded for , that current path is replaced with this  path. The  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  and , we can stop the search after line 15 if  (if the current node  is the target node).
Now we can read the shortest path from  to  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  is the list of vertices that make up one of the shortest paths from  to . If a path from  to  does not exist, sequence  will be empty.