Dijkstra's algorithm runs on a fee graph with one negative-cost leg but no negative cycle — can you trust its output?

## The review context A diff routes couriers over a fee network and computes cheapest routes with Dijkstra's algorithm. Someone has added a leg with a **negative** cost — a refund, a subsidy, a partner credit. The author's defence in the pull request is the standard one: *"Dijkstra only breaks on negative cycles, and there are none here — the graph is a DAG."* That defence is wrong, and this is a review you should block. ## Why one negative edge is already fatal The correctness argument for finalizing the smallest-tentative-cost vertex `v` runs: any rival route must leave the settled set at some unsettled vertex `u`, its prefix costs at least `dist[u]`, and `dist[u] >= dist[v]` because `v` was the minimum. The final step is the one that matters here — *the rest of the route, from `u` to `v`, costs at least 0*. That step, and only that step, uses non-negativity. Delete the assumption and the chain breaks: a suffix that subtracts can drag the total below `dist[v]`, so `dist[v]` was never safe to freeze. Notice how little that requires. It needs one edge with a negative cost positioned so that it is discovered *after* its target has already been settled. No cycle is involved. ## The minimal counterexample Three depots. Directed legs: | leg | fee | | --- | --- | | `S -> A` | 1 | | `S -> B` | 2 | | `B -> A` | -2 | True cheapest cost from `S` to `A`: `min(1, 2 + (-2)) = 0`. Trace the algorithm: settle `S` at 0, giving tentative `A = 1`, `B = 2`. The smallest unsettled value is `A` at 1, so `A` is settled and declared final. Then `B` settles at 2 and relaxes `B -> A` to 0 — but `A` is out of the unsettled set, and the reported answer stands at **1**. The graph has three vertices, three edges, and no cycle of any kind. This example is worth memorising: it is small enough to draw on a whiteboard mid-review and it kills the negative-cycle defence outright. ## Negative edge versus negative cycle These are distinct failures and conflating them is the core misconception: - A **negative edge** (no negative cycle) means cheapest routes still exist and are well-defined — the greedy settle-once strategy just computes some of them wrongly. Answers come out as **over-estimates**, never under-estimates, because every recorded value is the cost of a route that genuinely exists. - A **negative cycle** reachable on the way to a destination means there is no cheapest route at all: you can lap the cycle forever and drive the cost down without bound. The question itself becomes ill-posed, and the correct behaviour is to *detect and report* the cycle rather than return a number. ## Why it is dangerous rather than merely wrong The failure is silent. Nothing throws, nothing loops forever, and the algorithm terminates in its usual time. Only routes where a negative leg happens to fall after an already-settled vertex are affected, which is often a small minority — so unit fixtures with two or three well-behaved routes pass, and the bad numbers surface as slow revenue drift or as customer disputes over quoted fees. Silent, input-dependent, partially-correct output is the worst possible shape for a bug. ## The remedies, and one trap 1. **Re-model so no cost is negative.** Often the cleanest fix: fold refunds into the leg they offset, or represent them as a separate quantity rather than as edge weight. If you can prove every weight is non-negative, the greedy algorithm and its settle-once speed are back on the table. 2. **Use an algorithm that tolerates negative weights**, such as Bellman-Ford, which also reports the negative-cycle case instead of silently returning nonsense. 3. **Reweight with potentials** — assign each vertex a potential and replace each cost `c(x, y)` with `c(x, y) + p(x) - p(y)`. Because the potential terms telescope along any route, every route between a fixed pair changes by the same constant, so the cheapest route is preserved. Choose potentials that make all adjusted costs non-negative and the greedy algorithm becomes valid again. This is the idea behind Johnson's approach for all-pairs work. 4. **Allow re-settling** — put a vertex back into the unsettled set whenever its cost improves. This does yield correct answers when no negative cycle exists, but you have abandoned the settle-once bound, and adversarial inputs can drive the work up exponentially. Do not ship it as "Dijkstra with a small tweak". **The trap:** adding a constant `C` to every edge to lift the negatives away is *not* a valid fix. Shifting each edge by `C` adds `C` times the **hop count** to a route, so routes with more legs are penalised more and the cheapest route can change. Only the telescoping potential adjustment in option 3 leaves the ranking intact. ## A useful contrast Negative weights are harmless to minimum-spanning-tree construction, because its safe move is a *comparison* between two edge weights, not an accumulation along a path. Candidates who have internalised "greedy plus negative numbers equals trouble" as a blanket rule get this wrong in the other direction. The precise rule is narrower: greedy shortest-path search breaks under negative weights because its safety argument sums costs along a route.