Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

(“Dijkstra’s Algorithm” 2022)

Dijkstra’s algorithm is a Greedy Best-first search algorithm.

## Algorithm

Dijkstra’s algorithm uses Dynamic programming. Since we re-use previously-computed information (i.e. the distance up to the current point).

### Single-source shortest path problem

- Mark all nodes as unvisited; create an empty visited
`set`

- Set a temporary distance of infinity for all nodes except for the source which has a distance of 0
- Push all nodes onto the minqueue
- Work through the minqueue: mark nodes visited and update their non-visited children if the potential distance is less than the currently known distance
- Return the mapping of distances and previous nodes

Dijkstra’s algorithm implementation in Python

### Single-pair shortest path problem

Same as the single-source solution, but stop when you’ve found the target node.

## Time complexity

- \(\bigtheta((|E| + |V|)\log|V|)\), or \(\bigtheta{|E|\log(|V|)}\) for a connected graph, when implemented with a Binary heap.
- \(\bigtheta(|E| + |V|\log|V|)\) when implemented with a Fibonacci heap.

## Backlinks

- Single-pair shortest path problem
- Bellman-Ford algorithm
- Directed acyclic graph
- Single-source shortest path problem
- Dijkstra’s algorithm implementation in Python
- Dynamic programming
- Shortest path algorithm
- Branch and bound
- Contraction hierarchies
- Customizable route planning
- Topological order
- A-star search algorithm