Dijkstra's Algorithm Step by Step: The Heap, the Relax, the Proof

Most explanations of Dijkstra's algorithm stop at "use a priority queue and always take the closest node". Correct, and almost useless when you sit down to write it: it skips what goes into the heap, why an entry can be out of date, and why the node you pop is safe to call finished.

This article walks one small graph from the first pop to the last, then turns the trace into code and checks it against a brute force that cannot be wrong.

The problem it solves

A directed graph has edge costs — milliseconds, kilometres, euros — all zero or more. From one source you want the cheapest total cost to every other node, and the route behind it.

Breadth-first search answers this when every edge costs the same. The moment costs differ, fewest hops and cheapest route come apart. In the graph below, edge reaches hub in one hop for 9, or in two hops through relay for 2 + 3 = 5. BFS would lock in the one-hop route and never look back.

The graph used throughout:

• edge → hub costs 9, edge → relay costs 2
• relay → hub costs 3, relay → core costs 8
• hub → core costs 1

The intuition

Every node carries a tentative distance: the cheapest route found so far, starting at ∞. The heap holds pairs of (tentative distance, node), and the algorithm repeats one move — pop the smallest pair, and relax each outgoing edge: if going through this node is cheaper than what the neighbour currently has, overwrite the neighbour's distance and push the new pair.

Here is the whole run, one pop at a time.

1. Start: edge is 0, everything else ∞. Heap: (0, edge).
2. Pop (0, edge). Relax: hub becomes 9, relay becomes 2. Heap: (2, relay), (9, hub).
3. Pop (2, relay). Relax: hub improves from 9 to 5, core becomes 10. Heap: (5, hub), (9, hub), (10, core).
4. Pop (5, hub). Relax: core improves from 10 to 6. Heap: (6, core), (9, hub), (10, core).
5. Pop (6, core). No outgoing edges. Heap: (9, hub), (10, core).
6. Pop (9, hub). But hub is already 5 — this entry was pushed before the cheaper route turned up. Skip it.
7. Pop (10, core). Same story. Skip. The heap is empty; the answer is edge 0, relay 2, hub 5, core 6.

Steps 6 and 7 are what first implementations miss. Python's heapq cannot lower the priority of an entry already inside it, so the algorithm pushes a second, better pair and lets the old one go stale. When a stale pair surfaces, its distance exceeds the recorded one, and it is thrown away.

Why is the popped node final? Suppose hub is popped at 5 and some cheaper route to it existed. That route has to leave the set of finished nodes at some point, through an edge into an unfinished node x. x's tentative distance is at most the cost of the route up to it, which is at most the full route's cost, which is less than 5 — so x would have been popped before hub. Contradiction. The argument needs one thing: that the rest of the route cannot make the total smaller. That is exactly the non-negative-weights requirement.

Watch it run

The animation is the same four-node graph. The number above each node is its tentative distance, the strip underneath is the heap, and a node turns green the moment it is popped for real. Watch hub drop from 9 to 5 while its old 9 entry is still sitting in the heap. The animation tidies such leftovers away once a node is finished; the code below does the equivalent by skipping them when they surface.

The code

Two additions over the bare version: a parent map so the route can be rebuilt, and a counter for the stale pops from steps 6 and 7.

import heapq

def dijkstra(graph, source):
    dist = {node: float("inf") for node in graph}
    parent = {source: None}
    dist[source] = 0
    heap = [(0, source)]
    stale = 0
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            stale += 1                  # an older, worse entry for a finished node
            continue
        for nxt, w in graph[node]:
            if d + w < dist[nxt]:       # relax: a cheaper route to nxt
                dist[nxt] = d + w
                parent[nxt] = node
                heapq.heappush(heap, (dist[nxt], nxt))
    return dist, parent, stale

def path_to(parent, target):
    if target not in parent:
        return None                     # never reached
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

g = {"edge": [("hub", 9), ("relay", 2)],
     "relay": [("hub", 3), ("core", 8)],
     "hub": [("core", 1)],
     "core": []}
dist, parent, stale = dijkstra(g, "edge")
print(dist)                  # {'edge': 0, 'relay': 2, 'hub': 5, 'core': 6}
print(path_to(parent, "core"))   # ['edge', 'relay', 'hub', 'core']
print(stale)                 # 2

Parent pointers are overwritten on every successful relaxation, so following them backwards from a finished node spells out a shortest path.

To check that the trace generalises, compare against a brute force that enumerates every simple path. It is exponential, which is exactly what makes it a trustworthy referee on small graphs:

import random

def brute(graph, source):
    best = {node: float("inf") for node in graph}
    def walk(node, cost, seen):         # every simple path, no cleverness
        best[node] = min(best[node], cost)
        for nxt, w in graph[node]:
            if nxt not in seen:
                walk(nxt, cost + w, seen | {nxt})
    walk(source, 0, {source})
    return best

random.seed(7)
ok = True
for _ in range(2000):
    n = random.randint(1, 7)
    g = {i: [] for i in range(n)}
    for a in range(n):
        for b in range(n):
            if a != b and random.random() < 0.4:
                g[a].append((b, random.randint(0, 9)))
    ok &= dijkstra(g, 0)[0] == brute(g, 0)
print(ok)                    # True

Two thousand random graphs, including zero-cost edges and unreachable nodes, all agreeing.

The complexity

Each edge can cause at most one push, so the heap sees at most E pushes and E pops, each costing O(log E). Since E is at most V², log E is at most 2 log V, and the total is the familiar O((V + E) log V). Memory is O(V + E) in the worst case because of the stale entries.

On a dense graph, where E approaches V², the heap stops paying for itself; the array version that scans for the nearest unfinished node is O(V²) and simpler.

Where it goes wrong

• Finishing a node when it is pushed, not when it is popped. This is BFS with a heap bolted on. On the example it keeps hub at 9 forever. On the same 2,000 random graphs, that version disagrees with the brute force on 360 of them.
• Negative edges. The proof above leans on "the rest of the route cannot make the total smaller". A negative edge breaks exactly that sentence; use Bellman-Ford instead.
• Dropping the stale check. Distances stay correct, but every stale pop re-relaxes a finished node's edges for nothing.
• Ties on uncomparable nodes. If two entries share a distance, Python compares the second element. Node objects without an ordering raise a TypeError; push (dist, counter, node) to break ties by insertion order.
• One target only. Return the moment it is popped; it is final from then on.

How to say it in an interview

"I keep a tentative distance per node and a min-heap of (distance, node). I pop the smallest, skip it if it's stale, and relax its outgoing edges, pushing any improvement. A popped node is final because every other route to it goes through a node that's at least as far, and with non-negative weights the rest of that route can only add. With a binary heap that's O((V + E) log V)."

Then trace a few pops on the interviewer's example out loud. Pointing at the first stale entry before they ask is the clearest signal that you have actually written this.