Negative edge weights
A Socratic walk-through of negative edge weights — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does taking the cheapest next step always work until one road costs less than nothing?
Dijkstra's method for shortest paths is almost embarrassingly simple: keep a tentative distance for every place, repeatedly take the unvisited place with the smallest tentative distance, declare it settled, and use it to improve its neighbours. Greed, applied without apology, and it is provably right.
Greed is not usually right. Take the cheapest next move in most problems and you will regret it later. So the interesting question is not "how does Dijkstra work" but: what property of roads makes local greed globally safe here — and what exactly breaks when a road pays you to travel it?
Reasoning it through
REASONING #Find the step that carries the weight. When the algorithm pops the unsettled node u with the smallest tentative distance and declares it final, that is the only claim it ever makes. Everything else is bookkeeping. Why should that claim be true?
Suppose some cleverer path to u exists, shorter than the tentative value. Trace it from the source. It begins inside the settled region and must at some point step out of it, and call the first unsettled node it reaches v. Now v's tentative distance is already at least as large as u's — u was the smallest, that is why it was chosen. And the rest of the clever path, from v onward to u, contributes some further amount. If that amount cannot be negative, the clever path costs at least u's tentative distance, so it is not shorter after all. The claim holds.
Notice where non-negativity entered: once, in that final sentence, and nowhere else. It is not a convenience for the implementation. It is the entire proof.
So remove it and watch. Three places — S, A, B. The road S to A costs 1, S to B costs 2, and B to A costs −2, perhaps a delivery that pays more than the fuel. What is the cheapest way from S to A? Going direct costs 1. Going by way of B costs 2 + (−2) = 0. Zero is cheaper.
Now run the greedy method. From S the tentative distances become A at 1 and B at 2. The smallest is A at 1, so A is settled at 1 and never revisited. B is settled next at 2, and relaxing B to A would offer 0 — but A is finished. The answer returned is 1, and the truth is 0. The algorithm failed on a graph with three nodes.
Look at what the counterexample exploited. Greed assumes that a path already longer than your best cannot become shorter by continuing. Negative edges make that false: distance stops being monotone along a path, so "further along" no longer means "more expensive", and the ordering the algorithm settles nodes in stops meaning anything.
Take it one step further and even the question dissolves. If some cycle has negative total weight, walk around it repeatedly and the cost falls without limit — there is no shortest path, only an infimum of minus infinity. That is a different failure from the one above, and worth keeping separate: my three-node example has no cycle at all, and still defeats Dijkstra.
What survives, then? Abandon settling and simply relax. Any shortest path visits each node at most once, so it uses at most V − 1 edges. Sweep over every edge, improving whatever it improves, and repeat V − 1 times: after the k*th sweep every shortest path of *k edges or fewer is correct, by induction on its length, so after V − 1 sweeps all are. That is Bellman-Ford, at cost proportional to V × E, and it makes no assumption about signs. A further sweep that still improves something proves a negative cycle exists.
The analogy
THE ANALOGY #Think of exploring a cave by always going to the nearest unexplored opening, paying out rope as you go. Every metre of rope is a metre you never get back, so the nearest opening really is the cheapest and sealing it behind you costs nothing. Now imagine one passage where the rope spools back onto the reel. The openings you sealed early may have been reachable more cheaply through a passage you had not yet found — and the order you sealed them in was never a ranking at all.
rope cannot really un-spool, which is precisely why the analogy has to strain to reach the interesting case, and it says nothing about the sharper pathology — a loop of passages that gives rope back on every circuit, where the notion of a cheapest route stops existing rather than merely being mis-found.
Clarifying the model
THE MODEL #Two corrections, and the first is the folklore.
Dijkstra's condition is stated wrongly all the time as "no negative cycles". That is Bellman-Ford's condition. Dijkstra needs every individual weight to be non-negative, which is strictly stronger, and the three-node graph above is the proof: no cycles whatsoever, one negative edge, wrong answer.
Second, the usual advice to remove negative weights by adding a constant to every edge does not work. Add 3 to each weight above and S→A costs 4 while S→B→A costs 8: the constant is charged per edge, so it penalises paths with more edges and can change which is shortest. What does work is Johnson's reweighting, which adds a quantity per node: w'(u,v) = w(u,v) + h(u) − h(v). Along any path the h terms telescope and only h(start) − h(end) survives, so every S-to-A path shifts by the same amount and the ranking holds. Taking h as the true distances from a virtual source gives h(S) = 0, h(B) = 0, h(A) = −2, and the three weights become 3, 2 and 0 — all non-negative, with Dijkstra now correctly preferring S→B→A. Its honest limit: those potentials need one Bellman-Ford run, so the method pays for the harder algorithm once and then runs the cheap one many times.
What observation would refute the whole account? The load-bearing claim is that a settled node is final. Instrument the algorithm to shout whenever a node's distance improves after it was settled. Run it on any graph with all weights non-negative and it will never shout, however adversarial the graph, because the argument above forbids it. Feed it one negative edge and it shouts on the three-node example. A single non-negative graph in which it shouted would demolish the proof.
A picture of it
THE PICTURE #How to readStart at the rounded terminal, the source. The two edges leaving it are ordinary roads with their costs; the edge from B back to A is the negative one, drawn as a back-edge because that is exactly the direction the algorithm has already stopped looking in. The diamond is the single claim Dijkstra makes, and its two labelled branches are the two answers to it: the red box is what greed returns once A has been sealed at 1, the green box what the graph actually contains. Both branches are true statements about the same run, which is the defect.
What became clearer
WHAT CLEARED #Greed is safe here for one reason only: with non-negative weights, going further along a path can never make it cheaper, so the node with the smallest tentative distance cannot be improved by any route still under construction. That single property is the whole proof, and one edge below zero withdraws it — not slowing the algorithm but making it wrong, on a graph of three nodes and no cycles. What replaces it is patience rather than cleverness.
Where to go next
ONWARD #- Why A\* needs a consistent heuristic, and how that is the same non-negativity condition wearing different clothes.
Key terms
TERMS #| Term | What it means |
|---|---|
| Settled node | one whose distance Dijkstra has declared final and will not revisit; the assumption that fails under negative weights. |
| Negative cycle | a loop of total weight below zero, around which cost falls without limit, so no shortest path exists. |
Every term the collection defines is gathered in the glossary.