Why does Dijkstra only need to check each node once?
The proof that Dijkstra's one-shot extraction is correct: the invariant maintained by the priority queue, the role of non-negative edge weights, and the geometric meaning of the settled frontier.
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 8 scenes and explore, respond, and learn as you go.
Why is the first distance extracted from the priority queue in Dijkstra's algorithm guaranteed to already be the true shortest distance?
Dijkstra's algorithm famously labels each node's shortest distance 'final' the moment it pops off the priority queue — a single check, no second chances.
If the first popped distance were not truly minimal, the algorithm would silently lock in a wrong answer. Why can we be confident it always is?
A step-by-step simulation of Dijkstra exploring a weighted graph, with the priority queue visible and the 'locked-in' distance highlighted each round.
The shortest path to the popped node cannot be improved later because every unexplored path must cross a frontier edge whose remaining cost is non-negative — so the locked value is provably minimal.
A common guess is that Dijkstra works because it always picks the 'closest' next node — but closeness at extraction time is exactly what needs justification.
- Implementations with negative edge weights (Bellman-Ford territory)
- Complexity analysis or asymptotic comparisons
- Heuristic variants like A*
- Code-level pseudocode walkthroughs
- 01The 5-Node PuzzleslideQuestion
A weighted graph with five nodes is displayed. The classic Dijkstra execution is traced: at each step, one node is extracted from the priority queue and its distance marked final. The learner is asked to pinpoint the moment that guarantees correctness.
- Five-node weighted graph with a source node
- Priority queue contents shown before each extraction
- Extracted node is shaded as 'settled' with its distance frozen
- 02Commit to a ReasonquizPrediction
Before the mechanism is revealed, the learner chooses which invariant protects the popped distance from being beaten later.
- Make one independent choice about why the popped distance is already minimal
- 03Step the SimulatorinteractiveEvidence
An interactive simulation lets the learner manually advance Dijkstra on the same 5-node graph, watching the priority queue update and the frontier expand.
- Click 'Extract' to pop the smallest distance from the queue
- Observe the queue ranking of every remaining target distance
- Note that no extracted distance ever changes later
- 04Tracking a Rival PathslideEvidence
A second visualization overlays an attempted 'shorter' route to an already-settled node, showing that it must re-enter the frontier through an edge that adds non-negative cost — so it can never undercut the popped value.
- Highlight the settled node in gold
- Draw a rival route through the still-unsettled region
- Label the crossing edge with its non-negative weight
- 05Break It with a Negative EdgeinteractiveBoundary
The learner drags a slider to set one edge weight to a negative value and re-runs the simulation to watch a settled node's distance get beaten later — the single-check guarantee collapses.
- Slider sets one frontier edge to negative
- Simulator re-extracts and reveals the violated distance
- Confirms that non-negative weights are the load-bearing assumption
- 06The Frontier InvariantslideExplanation
A clean statement of the invariant: when a node is popped, every still-unexplored path to it must cross an unsettled edge, and that crossing can only add non-negative length. Hence the popped distance is already minimal.
- Formal statement of the invariant over the settled set S
- Role of non-negative edge weights in sealing the frontier
- Connection to a wavefront expanding outward from the source
- 07Apply It to a New GraphquizTransfer
A fresh weighted graph is shown. The learner picks which candidate from the priority queue can be safely settled next, applying the frontier reasoning to a new topology.
- Inspect the new graph and its current priority queue
- Identify the safe next extraction using the invariant
- 08Why One Check SufficesslideResolution
The driving question is answered directly: Dijkstra locks in a distance on first extraction because any later improvement would have to travel through a remaining, non-negatively-weighted edge, which cannot undercut what is already the queue's smallest value.
- Direct answer restating the frontier argument
- Non-negative weights as the necessary precondition
- Single-check settlement as a consequence, not an assumption
Discussion threads for a Stage aren't available yet.
This path ends here.
