Dijkstra with a Ticket Heap

This animation runs Dijkstra on a small weighted map. Every node wears a distance tag, starting at infinity except the source at 0. The min-heap is drawn as a sorted column of tickets on the right — each ticket is a claim: "I can reach this node for this cost."

Each step, the cheapest ticket flies from the top of the column to its node, and the node locks green — its distance is now final and will never change. Watch why that is safe: every other ticket in the column costs at least as much, and no path through a pricier node can circle back cheaper, because no edge has negative weight.

After each lock-in, relaxation pulses run along the node's outgoing edges. When a pulse reaches a neighbor whose tag can improve, the tag flips with a counter-roll to the smaller number and a fresh ticket drops into the heap.

Two things to track. First, one node can accumulate several tickets — only the cheapest matters, and stale tickets that arrive at an already-green node fizzle out harmlessly. Second, nodes lock in ascending order of final distance: the greedy order is the sorted order of answers.