Dijkstra's Shortest Path, in depth: the algorithm as an event stream, a frame-by-frame trace, and rendering the wavefront

Dijkstra as a stream of events

The ordinary way to write Dijkstra hides the interesting moments inside a loop. To animate it, turn every interesting moment into an event the loop emits, and let a separate renderer decide what to draw. There are five event kinds, and naming them is most of the insight:

• push — a node enters the priority queue with a tentative distance.
• pop_settle — a node comes off the queue for the first time; its distance is now final.
• pop_stale — a node comes off the queue but was already settled; this entry is a leftover and is discarded.
• relax_improve — an edge found a shorter route to a neighbour, so its tentative distance drops and a new queue entry is pushed.
• relax_skip — an edge was examined but offered no improvement.

The whole run is the sequence of these events. An animation is just a renderer walking that sequence one step at a time. A unit test is an assertion over it. A performance report is a histogram of it. Separating the algorithm from the rendering is the single idea that makes everything else in this article possible.

The graph we will trace

The adjacency list, source S:

graph = {
    "S": [("A", 4), ("B", 2)],
    "A": [("C", 5)],
    "B": [("A", 1), ("C", 8), ("D", 7)],
    "C": [("E", 2), ("T", 6)],
    "D": [("E", 1), ("T", 3)],
    "E": [("T", 4)],
    "T": [],
}

The graph is small enough to trace by hand but has the two features that make an animation worth watching: a node (A) that gets a better distance after its first push, creating a stale queue entry, and two competing routes to T (via C and via D) that resolve in a non-obvious order.

The algorithm, instrumented

Here is Dijkstra written as a generator. It is the textbook lazy-deletion version — push a fresh entry on every improvement, skip entries for already-settled nodes — with one addition: every decision is yielded as an event. The control flow is identical to the uninstrumented version, so you are watching the real algorithm, not a teaching mock-up.

import heapq

def dijkstra_events(graph, source):
    dist = {source: 0}
    prev = {}
    settled = set()
    heap = [(0, source)]
    yield ("push", source, 0, None)
    while heap:
        d, u = heapq.heappop(heap)
        if u in settled:                      # leftover entry: lazy deletion
            yield ("pop_stale", u, d, None)
            continue
        settled.add(u)
        yield ("pop_settle", u, d, dict(dist)) # d is now final for u
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")): # strict improvement only
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
                yield ("relax_improve", v, nd, u)
            else:
                yield ("relax_skip", v, nd, u)

The two lines that carry all the subtlety are the if u in settled guard and the strict nd < dist.get(v, inf) test. The first is what makes stale entries harmless: we never delete from the heap, we just ignore entries we have already finalised. The second is why a tie (an equal-length alternative route) never triggers a pointless re-push.

The trace, frame by frame

Running dijkstra_events(graph, "S") and listing only the pop events gives the frames below. The heap column shows the queue contents as a sorted multiset after that frame's relaxations — note that this is the sorted content, not heapq's internal array order, which is an implementation detail you should never rely on.

The totals are worth memorising as a sanity check for your own implementation on this graph: seven settles (one per node), three stale pops, ten pushes counting the source, and nine improving relaxations (one push each, plus the source push). The final distances are S=0, B=2, A=3, C=8, D=9, E=10, T=12, and the shortest route to T is S→B→D→T, not either of the routes through C.

Stale entries: watching lazy deletion

Frames 4, 7 and 10 are the ones beginners find mysterious, and an animation makes them obvious. Node A is pushed at distance 4 (from S), then at frame 2 we find a shorter route S→B→A and push A again at distance 3. Both entries sit in the heap. The distance-3 entry pops first and settles A; the distance-4 entry pops later, finds A already settled, and is discarded. Nothing was ever deleted from the heap — the stale entry was simply out-voted by a better one that reached the front first.

This is lazy deletion, and it is why the queue can hold more entries than there are nodes. The alternative, a decrease-key operation on an indexed heap, keeps exactly one entry per node but needs a heap that supports position lookups. For most graphs the lazy version is faster in practice and far simpler; the cost is that your heap size is bounded by the number of edges, not the number of nodes. When you animate it, stale pops show up as frames where nothing changes — a visual hiccup that is completely correct.

Reading the wavefront

The deepest intuition an animation gives you is the wavefront. Watch the settle events in order: S@0, B@2, A@3, C@8, D@9, E@10, T@12. The distances never decrease. That is not a coincidence of this graph; it is the core property of Dijkstra on non-negative weights, and it has two practical consequences. First, once a node is settled its distance is final, so you never revisit it. Second, the moment your target T is settled you can stop — everything still in the queue has distance at least T's, so no later frame can improve it. Early termination on T turns a full single-source search into a point-to-point one for free.

A per-frame invariant checker

Because the algorithm is now a stream, you can assert properties on every frame instead of only checking the final answer. This is how you catch a bug the instant it happens rather than discovering a wrong distance at the end. Three invariants hold at every pop_settle frame — two inside the checker below, plus the non-decreasing settle order the driver loop enforces:

INF = float("inf")

def check_frame(dist, settled, graph):
    # 1. Every settled node has a finite, known distance.
    for u in settled:
        assert dist.get(u, INF) < INF, f"settled {u} has no distance"
    # 2. No edge leaving a settled node can shortcut another settled node;
    #    if it could, we settled something too early.
    for u in settled:
        for v, w in graph[u]:
            if v in settled:
                assert dist[v] <= dist[u] + w, f"edge {u}->{v} violates settle"

prev_d = -1
for ev, nodename, d, snap in dijkstra_events(graph, "S"):
    if ev == "pop_settle":
        assert d >= prev_d, "settle distances must be non-decreasing"
        prev_d = d
        check_frame(snap, {k for k in snap if snap[k] <= d}, graph)

The non-decreasing check on settle distances is the cheapest and most valuable of the three. If it ever fires, you have either a negative edge (which Dijkstra cannot handle — use a cost-model engine or Bellman-Ford instead) or a bug in your heap comparison. Wiring this assertion into your test suite means a regression announces itself as a failed invariant, not as a silently wrong route in production.

Rendering frames: text first, SVG later

A renderer consumes events and produces frames. Start with text — it is enough to debug the whole algorithm and costs nothing to run in CI:

def render_text(snap, settled, u, d):
    cells = []
    for n in sorted(snap):
        mark = "*" if n in settled else " "   # * = settled
        cells.append(f"{n}{mark}{snap[n]}")
    return f"settle {u}@{d}  |  " + "  ".join(cells)

# the settle-C frame prints this (E and T are not in dist yet, and D is
# reached but not settled, so it shows with a space instead of a *):
# settle C@8  |  A*3  B*2  C*8  D 9  S*0

The text renderer is the ground truth: it is deterministic, diff-able and trivial to assert against. An SVG or canvas renderer is a cosmetic layer on top of exactly the same event stream — it maps each node to a coordinate, colours settled nodes one way and frontier nodes another, draws the current node's outgoing edges as it relaxes them, and advances one frame per event. Because the renderer never touches the algorithm's state, you can swap a static diagram for an interactive scrubber without changing a line of the search. Keep the two apart and the animation is a view, not a fork.

What BFS and A* look like as animations

The event model generalises, and seeing the differences animated is the fastest way to understand them. Breadth-first search is Dijkstra with every edge weight equal to one and a plain FIFO queue instead of a binary heap: its wavefront is a set of perfect concentric rings, one per hop, and it never produces a stale entry because a node's first discovery is always its best. A* keeps Dijkstra's machinery but orders the queue by d + h(v), where h is an admissible estimate of the remaining distance to the goal. Animated side by side on the same graph, A*'s wavefront is visibly lopsided — it bulges toward the target and barely explores away from it, which is exactly the behaviour you want and exactly what the heuristic buys. If you ever animate A* and the wavefront is symmetric, your heuristic is returning zero and you have reinvented Dijkstra.

Failure modes the animation exposes

Every one of these is visible in the trace long before it corrupts the final answer, which is the whole argument for treating the algorithm as a stream.

What to do next

1. Copy the dijkstra_events generator and reproduce the ten-frame trace above; confirm you see three stale pops and a final distance of 12 to T.
2. Add the per-frame invariant checker to your test suite and run it on a graph with a known-correct answer, then deliberately flip the strict < to <= and watch the event stream change: on this graph pushes rise from 10 to 11, stale pops from 3 to 4, and prev[E] flips from C to D on the tie.
3. Write the text renderer first and snapshot its output as a golden file; only then build an SVG or canvas view on top of the same event stream.
4. Swap the heap for a FIFO queue and unit edge weights to get BFS for free, and confirm the wavefront becomes concentric rings.
5. Add an admissible heuristic to the priority to get A*, animate it against plain Dijkstra on the same graph, and measure the drop in settled nodes.
6. For negative edges or exotic cost models, stop reaching for Dijkstra and read the cost-model engine article instead.