Which Dijkstra invariant breaks when one link in a latency graph has a negative weight?

## The scenario A network-routing service picks paths across a provider mesh, with each link weighted by measured latency in milliseconds. A commercial team introduces a promotional peering link and models the rebate as a **negative** weight of -8, so that routes crossing it look cheaper. The existing shortest-path service keeps running, produces routes, and reports no errors. Someone asks whether the results are still trustworthy. They are not, and the reason is one specific invariant. ## The invariant Dijkstra maintains a settled set and a frontier. Its correctness claim is: > **When a vertex `u` is extracted with the minimum tentative distance `d`, `d` is the true shortest distance to `u`, and it will never change again.** The justification is entirely about the sign of the remaining weights. Any route to `u` other than the one already found must at some point cross from the settled region into the frontier, at some vertex `x` whose key is at least `d` (otherwise `x`, not `u`, would have been extracted). From `x` onward the route accumulates more weight, and if every weight is `>= 0`, the total can only grow. So no alternative route can beat `d`. Remove non-negativity and the last step collapses. From `x` onward the route can now accumulate **less** - the rebate link - so a route that looked worse at the frontier can arrive at `u` cheaper than `d`. Dijkstra has already declared `u` settled and moved on. ## Why the damage spreads A settled vertex is not merely a wrong number in a table; it is a **source of relaxations**. Every vertex settled after `u` may have had its distance computed from `u`'s inflated value. A single negative edge in a mesh of thousands of links can therefore produce a distance table where many entries are too large, and the errors are not localized near the negative link. This is what makes it dangerous rather than merely imprecise: you cannot look at the output and see which entries to distrust. ## What actually happens at runtime Three things that do **not** happen, all of which candidates guess: - It does not crash or raise an error. No implementation checks the sign. - It does not loop forever. Each vertex is settled once, so the loop still terminates. - It does not merely become slower. The bound is unchanged; the *answers* are wrong. The failure mode is a completed run with plausible-looking numbers. That is the worst kind. A variant worth knowing: if you drop the settled check and allow a settled vertex to be **reopened** when a smaller distance appears, correctness can be restored as long as there is no negative cycle - but you lose the performance guarantee entirely, and adversarial graphs drive the number of reopenings to exponential. "Just reopen nodes" is not a fix you can ship on an unbounded graph. ## The reweighting trap The most common wrong fix: *"add 8 to every link so nothing is negative, then run it as before."* This changes the problem. Adding a constant `C` to every edge charges a route `C` times its **hop count**, so a 2-hop route gains `2C` while a 5-hop route gains `5C`. Short-hop routes are systematically favoured, and the algorithm returns the shortest route under a different cost function than the one you asked about. On the latency mesh, a two-hop transcontinental link would start beating a five-hop chain of fast local links regardless of actual milliseconds. (There *is* a correct reweighting technique for negative-weight graphs, one that shifts each edge by a per-vertex potential rather than a global constant so that route costs shift uniformly - but it needs those potentials computed first by a method that tolerates negative weights, so it is not a way to avoid the problem.) ## What to say when a skeptic pushes back The skeptic's line is "shortest paths exist in this graph, so a shortest-path algorithm should find them." The answer is that existence of shortest paths is not the precondition Dijkstra needs. What it needs is that **extending a route never makes it cheaper** - that is the assumption baked into settling the frontier minimum. A graph can have perfectly well-defined shortest paths and still violate that assumption. When it does, reach for an algorithm designed for negative weights, such as Bellman-Ford, and accept its different cost profile; the details of that algorithm are a separate discussion. One honest boundary case: if the negative edges all leave the **source** and nothing else is negative, the greedy order happens to survive. Do not build a production argument on that - it is a fragile property that the next topology change deletes.