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.