In Dijkstra's algorithm, why can the closest unsettled vertex be finalized immediately?
answer
- consider any rival route to that vertex
- it must exit the settled set somewhere
- look at the first unsettled vertex on it
- that vertex's tentative cost is not smaller
- the remaining legs can only add
basics
~20 sAny rival route must first leave the settled set through some unsettled vertex whose tentative cost is already at least as large, and with non-negative edge weights the rest of that route can only add cost.
solid answer
~50 sThe greedy claim is: when you pick the unsettled vertex `v` with the smallest tentative cost, that cost is already final. Here is the argument, over a courier network where each leg charges a non-negative fee. Any route from the depot to `v` must at some point step out of the settled set for the first time, at some unsettled vertex `u`. The prefix of that route reaching `u` has already been accounted for, so it costs at least `dist[u]`. But `v` was chosen as the *smallest* tentative cost, so `dist[u] >= dist[v]`. The remaining legs from `u` onward cost zero or more, so the whole alternative route costs at least `dist[v]`. No route can beat what we already have, so `v` is safe to settle and never needs revisiting. Non-negativity is doing real work in that last step.
code
pseudocode · 11 linesfor each vertex u:
dist[u] = infinity
dist[source] = 0
unsettled = all vertices
while unsettled is not empty:
v = vertex in unsettled with minimum dist[v]
remove v from unsettled // dist[v] is now claimed final
for each edge (v, w) with cost c:
if dist[v] + c < dist[w]:
dist[w] = dist[v] + cgo deeper
Be ready to describe the two sets — settled versus unsettled — and to say that the algorithm repeatedly finalizes whichever unsettled vertex currently has the smallest tentative cost.
Explain the invariant and produce the argument out loud: any rival route leaves the settled set at some unsettled vertex whose cost is already at least as large, and the remaining legs only add.
Demonstrate that you know which assumption is load-bearing. Be able to say that non-negativity is used exactly once, and to treat a settled value later improving as a correctness alarm worth halting on.
Own the consequences of the invariant at system scale: vertices finalize in non-decreasing cost order, so partial results are usable early — and that guarantee is exactly what you lose if anyone lets a negative-cost edge into the model.
## What the algorithm is claiming Run the fragment above over a courier network: vertices are depots, edges are legs, and each leg charges a non-negative fee. Two sets exist at all times — **settled** vertices, whose cost is declared final, and **unsettled** ones, whose `dist` is only a **tentative** upper bound: the cheapest route found *so far* using only settled intermediate stops. The single greedy move is the line `v = vertex in unsettled with minimum dist[v]`, immediately followed by removing `v` for good. That is a strong claim. Nothing has looked at most of the network yet; why is it allowed to say "this number will never improve"? ## The invariant **Invariant.** At the top of each loop iteration, `dist[x]` is the true cheapest cost from the source for every settled `x`, and for every unsettled `y`, `dist[y]` is the cheapest cost of a route whose intermediate stops are all settled. The interesting half is showing the invariant survives settling `v`. ## The proof, in one paragraph Let `v` be the unsettled vertex with the smallest tentative cost, and let `P` be *any* route from the source to `v`. The source is settled and `v` is not, so walking along `P` there is a **first** vertex that is unsettled; call it `u` (possibly `u == v`). Everything before `u` on `P` is settled, so the prefix of `P` ending at `u` is one of the routes the invariant already accounts for, and therefore costs at least `dist[u]`. Because `v` was chosen as the minimum over all unsettled vertices, `dist[u] >= dist[v]`. The remaining legs of `P`, from `u` to `v`, have non-negative fees, so they add at least 0. Chaining it: `cost(P) >= dist[u] >= dist[v]`. Since `P` was arbitrary, no route to `v` is cheaper than `dist[v]`, and `dist[v]` is itself the cost of a real route. It is optimal. Settle it. ## Where each assumption is used This is the part interviewers probe, because it is where the algorithm's fragility lives: - **"`v` is the minimum"** gives `dist[u] >= dist[v]`. Take away the minimum-selection rule and the argument collapses immediately — that is why the greedy choice is not an optimisation, it is the correctness argument. - **Non-negative fees** give "the rest costs at least 0". This is the *only* place non-negativity enters, and it is enough: a single negative leg makes the suffix able to subtract, and a settled vertex can then be undercut later. - **Nothing requires acyclicity.** Cycles are fine; with non-negative weights no cheapest route ever wants to go round one. - **Nothing requires connectivity.** Unreachable vertices simply stay at infinity. ## Wrong justifications that sound right - *"It works because the priority structure keeps things sorted."* The ordering structure is an implementation convenience for finding the minimum quickly. Scanning all unsettled vertices linearly to find the minimum is equally correct — slower, but correct. Sorting is not the reason. - *"It works because each edge is relaxed once."* Relaxing everything, repeatedly, is a *different* family of shortest-path algorithms and it does not need the settle-once claim at all. Dijkstra's efficiency comes precisely from *not* needing to redo work, and that comes from the invariant, not the other way round. - *"It works because the graph has no cycles."* Nothing in the proof mentions cycles. ## The operational consequence Because each vertex is settled exactly once, the algorithm's work is bounded and predictable, and its output can be consumed incrementally: vertices come out in non-decreasing order of final cost, so if you only need the ten cheapest destinations from a depot, you can stop after ten settlements. That property is a direct corollary of the invariant — and it silently disappears the moment the non-negativity assumption is violated, which is why a review of any routing change should start by asking whether every leg's cost can be proven non-negative. ## What an interviewer is listening for A middle-weight answer states the invariant and produces the "first unsettled vertex on the route" argument. The signal that separates a real understanding from a recited one is being able to point at the exact sentence where non-negativity is used — and to say what breaks if you delete it.
- Point at the exact step where the argument uses non-negative edge weights.In the final chaining step: after bounding the route's prefix by `dist[u] >= dist[v]`, you still have to dismiss the rest of the route from `u` onward, and that needs those remaining legs to contribute at least zero. The prefix bound alone proves nothing — a suffix allowed to subtract could bring the total below `dist[v]`.
- If a vertex's cost improves after it has been settled, what does that tell you?That an assumption has been violated. Under non-negative weights the invariant forbids it, so an improvement means either a negative-cost edge slipped into the graph or the selection step is not really picking the global minimum over unsettled vertices — a broken comparator or a stale key. It is a correctness alarm, not a rounding artefact.
- Does the argument require the graph to be acyclic or connected?Neither. Cycles are harmless because with non-negative weights no cheapest route benefits from going round one. Disconnected regions are harmless too: unreachable vertices keep an infinite tentative cost and are simply never usefully settled. The only structural requirement is that edge costs never go below zero.
saying these in an interview costs you the question
- It is correct because the graph has no cycles
- The ordering structure being sorted is what makes it correct
- Vertices can be settled in any order if all edges are relaxed
- A settled vertex may be settled again later
- Tentative distances are guesses rather than real route costs