Why Dijkstra's Nodes Stay Locked

Set up the driving question: Dijkstra extracts nodes one by one, but what guarantees that once a node is popped, its distance is final?

• Dijkstra marks each node as visited once it is extracted
• The shortest distance to a visited node never changes afterward
• We need to find the single reason this is always true

Before the trace, ask the learner to pick the rule they think is really doing the locking work.

• Choose what actually prevents a locked node from being improved

Walk through Dijkstra on a five-node graph with non-negative weights, showing the min-heap state, the tentative distances, and the extraction order.

• Each extraction picks the smallest tentative distance among unvisited nodes
• Relaxations only lower a neighbor's distance, never raise it
• Once a node is extracted, no later relaxation ever touches it

An interactive simulation where the learner attempts to relax an already-extracted node by routing through unvisited nodes, and watches the path length only grow.

• Only unvisited nodes remain in the priority queue
• Any detour through an unvisited node adds non-negative edge weight
• The locked node's distance cannot be beaten

State the core argument: any alternative path to a locked node must start with an edge from a locked node to an unvisited one, and every such edge contributes non-negative extra cost.

• A shortest path to a locked node must end with an edge from an unvisited node
• That edge's weight is at least 0, so the alternative path is at least as long
• The extracted distance is therefore the global minimum

Show what happens if the assumption fails: a single negative edge weight would let a longer-looking path overtake an already-locked node, which is why Dijkstra requires non-negative weights.

• Negative edge weights can shorten a path through an unvisited node
• Dijkstra's finalization argument assumes each remaining edge is non-negative
• This is exactly why Bellman-Ford is needed for negative weights

A new weighted graph with an obvious extracted order; the learner must identify which node settles next and confirm that no later relaxation can improve it.

• Identify the next extractable node
• Predict the final distance after extraction
• Verify that detouring through unvisited nodes cannot improve it

Directly answer: a node is locked because any competing path would have to enter it through an unvisited node via a non-negative edge, so the first extracted distance is already the shortest possible.

• The lock is a consequence of non-negative weights and the min-heap extraction order
• It is not a heuristic or a convenience — it is a guarantee
• This guarantee is what makes Dijkstra correct in O((V+E) log V)