Dijkstra's algorithm

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

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

Backlinks

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