Dijkstra's algorithm

Implement Dijkstra's algorithm with a min-heap to find shortest distances from a source, then reconstruct the full path.

Dijkstra's algorithm extends the relaxation idea from the previous lesson into a complete algorithm. The key guarantee: always relax from the node with the currently smallest known distance. A min-heap (priority queue) enforces that ordering efficiently.

The algorithm

Initialise dist[source] = 0, dist[v] = ∞ for all other nodes.
Push (0, source) onto a min-heap.
Pop the cheapest (d, u). If d > dist[u], this is a stale entry — skip it.
For each neighbour (v, w) of u, relax: if dist[u] + w < dist[v], update dist[v] and push (dist[v], v) onto the heap.
Repeat until the heap is empty.

The "stale entry" check replaces the need to update existing heap entries (which is expensive). Push a new entry instead; when you pop the stale one, discard it.

Implementation

Python — editable, runs in your browser

import heapq

def dijkstra(graph, source):
  """
  Returns (distances, predecessors).
  distances[v]    = shortest distance from source to v (inf if unreachable)
  predecessors[v] = the node before v on the shortest path from source
  """
  dist = {node: float("inf") for node in graph}
  dist[source] = 0
  pred = {node: None for node in graph}
  heap = [(0, source)]

while heap:
      d, u = heapq.heappop(heap)
      if d > dist[u]:
          continue                 # stale entry — skip
      for v, w in graph[u]:
          new_dist = dist[u] + w
          if new_dist < dist[v]:
              dist[v] = new_dist
              pred[v] = u
              heapq.heappush(heap, (new_dist, v))

return dist, pred

def reconstruct_path(pred, source, target):
  """Walk backwards through predecessors to recover the path."""
  path = []
  node = target
  while node is not None:
      path.append(node)
      node = pred[node]
  path.reverse()
  if path and path[0] == source:
      return path
  return []   # target unreachable from source

# ── Test graph ───────────────────────────────────────────────────────────────
#   0 --(4)--> 1
#   |          |
#  (1)        (1)
#   |          |
#   2 --(2)--> 1    2 --(5)--> 3
#
# Shortest paths from 0:
#   0 -> 0: 0
#   0 -> 1: 3  (via 2)
#   0 -> 2: 1
#   0 -> 3: 4  (via 2 -> 1 is 3, then 1 -> 3 is 1 = 4)

graph = {
  0: [(1, 4), (2, 1)],
  1: [(3, 1)],
  2: [(1, 2), (3, 5)],
  3: [],
}

dist, pred = dijkstra(graph, 0)
print("Distances from 0:", dist)
print("Path 0 -> 3:", reconstruct_path(pred, 0, 3))
print("Path 0 -> 1:", reconstruct_path(pred, 0, 1))

Complexity

Operation	Cost
Each node popped from heap	O(log V)
Each edge relaxed	O(log V) for the push
Total	O((V + E) log V)

This beats Bellman-Ford's O(VE) whenever the graph is sparse (E is not much larger than V).

Dijkstra's requires all edge weights to be non-negative. A single negative edge can cause it to miss the true shortest path because it commits to a "cheapest so far" without expecting prices to drop further. For negative weights, use Bellman-Ford instead.

Reconstructing the path

The pred dict records, for each node, which node we came from on the cheapest known path. To recover the path to a target, walk backwards through pred until you reach None (the source has no predecessor), then reverse.

If pred[target] is still None and target != source, the node is unreachable — return an empty list.

Where to go next

Next: topological sort — ordering nodes in a directed acyclic graph so every edge points "forward." A key tool for build systems, course prerequisites, and any domain with dependency ordering.

Finished reading? Mark it complete to track your progress.

The algorithm

Implementation

Complexity

Reconstructing the path

Where to go next

On this page