How Dijkstra Locks In Each Intersection Once

Frame the problem: a small city grid with intersections as nodes and streets (with travel times) as weighted edges. Ask why each intersection needs to be 'settled' exactly once, even though many possible routes reach it.

• Each node has many candidate routes, but Dijkstra settles each only once
• Question: what makes the first time a node is chosen also the final time?
• Focus on a single driving question, not on heap implementation

Show a small weighted graph and ask the learner to click which intersection they think Dijkstra will lock first, and why.

• Pick the node you expect to be settled first
• Reason from start distances, not from later hops
• Commit before seeing the algorithm run

Step-by-step animation frames showing each iteration: the priority queue, the node extracted as minimum, neighbors relaxed with updated distances, and the extracted node color-shifting from 'tentative' to 'locked'. A counter tallies locks per node.

• Every node is extracted from the priority queue exactly once
• On extraction, it flips from tentative to locked
• Neighbors' tentative distances shrink via relaxation
• No locked node is ever re-inserted

A static two-panel comparison: Panel A shows the frontier as a circle around the start, with the locked node at the center and all other unsettled nodes outside that radius. Panel B shows a hypothetical 'late' path arriving at the same locked node via an unsettled neighbor, with the neighbor shown to be farther from the start than the locked node already is.

• When node v is locked, every still-unlocked node has distance ≥ d(v)
• Any future path into v must pass through some still-unlocked node u
• Path through u would cost at least d(u) + w(u,v) ≥ d(v) + w ≥ d(v)
• So no future path can beat d(v)

Lay out the argument in plain terms: nonnegative weights, the priority queue always holds the smallest current tentative distance, and that smallest one cannot be undercut.

• Nonnegative edge weights: a step away cannot reduce distance
• Min-heap invariant: the top is the shortest tentative distance in the entire graph
• Locking fires at the queue's minimum, which is the global minimum among unsettled nodes
• Once locked, distance is permanent — that is why 'exactly once' is enough

Learner runs the same algorithm on a new graph where one edge is very long and another very short, and confirms each node still locks exactly once — verifying the explanation travels beyond the first example.

• Operate the algorithm on a fresh graph
• Watch the lock counter stay at one per node
• Notice: uneven weights do not break the once-per-node guarantee

Show one counterexample: an edge with negative weight. The frontier radius argument collapses because a still-unsettled path could now be shorter, so Dijkstra would settle a node, then later find a shorter path and need to 'unlock' it.

• Negative weights can make a later path through an unsettled node cheaper
• That is why a once-locked node would need to be updated again
• Bellman–Ford is the right tool when this happens
• Dijkstra's 'once and done' guarantee depends on nonnegative weights

Directly answer the driving question and tie the scenes together into a one-sentence mental model.

• Each intersection is locked exactly once: when it first becomes the minimum-distance unsettled node
• Because every still-unsettled node is at least as far as the locked one, no later route can undercut it
• The min-heap pulls each node out exactly once, and that extraction is the lock event
• Nonnegative weights are the quiet precondition that makes 'once' sufficient