Nearest first
A Socratic walk-through of nearest first — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does always exploring the closest place you have not yet visited find the shortest route to everywhere?
Greedy rules usually disappoint. Take the cheapest option at every step of a journey and you generally end up somewhere expensive, because the cheap first move led into costly country. So it should be suspicious that the classic shortest-path method is exactly that: repeatedly pick the nearest place you have not yet visited, declare its distance final, and never revisit it.
Why is this one greedy rule allowed to be right? And — the question that actually matters — under what condition does it stop being right?
Reasoning it through
REASONING #Let us be careful about what is being chosen greedily. The method is not choosing the next step of a route. It is choosing which subproblem is safe to close. At any moment you hold a set of places whose true distance you already know, and a frontier of places you have reached by some path but might yet reach more cheaply. Picking the nearest frontier place is a claim: no better path to this one will ever turn up.
Why would that claim hold? Suppose you are about to settle a place — call it the town — with a tentative distance of 9, and 9 is the smallest tentative value on the frontier. Now imagine some rival path to the town that you have not discovered, and ask where it goes. It starts inside the settled region and eventually arrives at the town, so somewhere along the way it must step out of the settled region for the first time. Call that first outside place the door.
What do we know about the door? It is on the frontier, because it is one step out of settled territory, so its tentative distance is already recorded — and since 9 was the smallest, the door's tentative value is at least 9. So the rival path has already spent at least 9 by the time it reaches the door. Then it still has to travel from the door to the town.
And here is the entire load-bearing step, in one clause: that remaining travel cannot make the total smaller, because no edge has negative length. The rival path costs at least 9 plus something non-negative, so it cannot beat 9. The claim holds, the town is settled, and the argument repeats.
Notice where the condition entered. Not in the priority queue, not in the bookkeeping — in one sentence about the tail of a hypothetical path. Remove non-negativity and that sentence collapses. Concretely: an edge from the start to B costing 5, an edge from the start to C costing 6, and an edge from C to B costing -4. Nearest-first settles B at 5 and never looks again, but the true distance is 2. The algorithm is not slightly wrong there; it is confidently wrong, and it reports a finished answer.
Does the frontier's own bookkeeping need justifying too? Slightly. When a place is settled, you relax its outgoing edges — offer each neighbour a possibly better tentative distance through this place. That is what keeps the door's recorded value honest. The two halves lean on each other: relaxation guarantees the frontier values are real path lengths, and the minimum-first rule guarantees the smallest of them is not merely real but optimal.
The analogy
THE ANALOGY #Think of ink dropped into a still sheet of blotting paper, spreading outward at a steady rate. The wavefront reaches the nearest point first, then the next nearest, and so on. When the ink arrives somewhere, that is the earliest it could possibly have arrived, because ink travelling any other way would have had to cover more paper. Settling a node in order of distance is simply reading off the order in which the stain touches each point.
blotting paper cannot have a stretch that un-spends time — a fibre that pulls the ink forward faster than it arrived — and that impossibility is exactly the assumption the analogy quietly smuggles in, so the picture gives you no warning at all about the one case where the algorithm fails.
Clarifying the model
THE MODEL #The misconception worth heading off is that this explores in order of distance from wherever it just was, like a traveller wandering to the next-closest town. It does not. Everything is ordered by distance from the source. The frontier can jump right across the map between iterations, and often does.
A second refinement: "finds the shortest route to everywhere" is really "finalises the nodes in increasing order of true distance". You get every destination for the price of one, which is why the method is not wasteful even when you only wanted one target — although if you do have a single target you can stop the moment it is settled, and you can bias the ordering with a lower-bound estimate of the remaining distance. That last move is A\, and it is instructive here: A\ stays correct precisely when the estimate is consistent, which is the condition that makes the internally reweighted edges non-negative again. The same threshold, wearing a different hat.
If you genuinely need negative weights, you need a different family. Bellman-Ford relaxes every edge repeatedly and takes longer, but it tolerates negative edges and detects negative cycles — which matter because with a negative cycle "shortest path" has no answer at all. Johnson's algorithm splits the difference by reweighting a graph into a non-negative one, then running nearest-first from each source.
A picture of it
THE PICTURE #How to readStart at the rounded source node and follow the solid arrows around the loop: the frontier store feeds the first diamond, the winner is settled, its edges are relaxed, and the improvements flow back into the store. Take the "no" branch of the second diamond only when nothing is left, which is where the rounded outcome sits. The dashed arrow leaving relaxation is the hazard, not part of the loop — it points at the one condition, negative edge weights, that invalidates the settle-and-never-revisit rule the whole cycle depends on.
What became clearer
WHAT CLEARED #Nearest-first is not greedy about the route; it is greedy about which answer is safe to freeze. The freeze is justified by a single argument — any rival path must cross the frontier, and crossing already costs at least as much as the node being settled — and that argument survives only because the remainder of the rival path cannot be negative. Non-negative weights are not a technicality in the fine print. They are the proof.
Where to go next
ONWARD #- Why Bellman-Ford needs V-1 passes, and what a V-th pass detects.
- How A\*'s admissible-versus-consistent distinction maps onto the same non-negativity condition.
- What changes when edge weights vary with time, as in transit routing.
Key terms
TERMS #| Term | What it means |
|---|---|
| Relaxation | offering a neighbour a shorter tentative distance via the node just settled. |
| Frontier | the reached-but-not-yet-finalised nodes, held in a priority queue keyed by tentative distance. |
| Dijkstra's algorithm | the nearest-first method itself, published in 1959; with a binary heap it runs in O((V + E) log V) time. |
| Bellman-Ford | the slower alternative that tolerates negative edge weights and reports negative cycles. |
| Negative cycle | a loop of total negative length, around which a path can be shortened indefinitely, so no shortest path exists. |
Every term the collection defines is gathered in the glossary.