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 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¶

1. Mark all nodes as unvisited; create an empty visited set
2. Set a temporary distance of infinity for all nodes except for the source which has a distance of 0
3. Push all nodes onto the minqueue
4. Work through the minqueue: mark nodes visited and update their non-visited children if the potential distance is less than the currently known distance
5. 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.

## Bibliography¶

“Dijkstra’s Algorithm.” 2022. Wikipedia, December. https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=1127202995.