Negative Costs and Reopening

1The assumption UCS lives on

Every guarantee in the cost-aware search lesson traces to one sentence: extending a path never lowers its cost. With every edge at least 0, the g of a path is non-decreasing as it grows, so work already popped can never be undercut by work still queued — that is the whole licence for settling a node on first pop.

State the licence carefully and you can see exactly how much it covers. It does not require costs to be large, or equal, or integer; zero-cost edges are fine. It requires only that no edge pays you back. The moment one edge is negative, 'cheapest so far' stops being a fact about the future and becomes a hope about it.

This is worth internalising as a proof habit: when an algorithm's correctness argument uses an assumption exactly once, the counterexamples all live exactly there. The next concept builds the smallest one.

Figure. Path cost g as a route grows, both routes starting at g = 0. The all-positive staircase never steps down, so anything settled earlier stays beaten. The staircase with one paying-back edge steps down mid-route — and everything settled before that step was settled on a false promise.

The licence and its limit

1. The invariantWith edges ≥ 0, g never decreases along any path, so pop order equals cost order.
2. Where it is spentThe cut argument uses it once: from the frontier onward, a rival path can only add.
3. What withdraws itA single negative edge lets a longer path finish cheaper than a settled one.

2One negative edge breaks settle-on-pop

Here is the smallest graph that defeats uniform-cost search. S reaches G directly for 9; S reaches A for 10; and the edge from A to G costs −8 — a rebate, a recovered joule, a subsidised leg. The best route is through A: 10 + (−8) = 2. UCS never finds it.

Trace the pop order to see the failure precisely. S pops at 0 and puts G at 9 and A at 10 on the frontier. G is cheaper, so G pops next — and the search settles it and stops, returning 9, while the path worth 2 still sits one expansion away. Nothing malfunctioned: settle-on-pop did exactly what its proof licenses, and the licence was void because one edge lowered a growing total.

Notice what the counterexample does not need: no negative cycle, no elaborate graph — three nodes and one honest rebate. Whenever your cost model can produce even one negative edge, the algorithm choice has to change before the map does.

Figure. The counterexample that breaks uniform-cost search: UCS expands G at cost 9 and stops, never learning that the expensive-looking detour through A totals 10 + (-8) = 2. "Cheapest so far" is only safe when no later edge can pay you back - which is why planning maps keep costs non-negative.

3Reopening: the repair and its price

The repair is mechanically small: stop trusting pops. Keep the best-known g per node, and when a cheaper path to an already-settled node appears, put the node back on the frontier and re-relax its successors — the settled set stops being permanent and becomes provisional. Algorithms that may revisit are called label-correcting, against the label-setting family (Dijkstra, UCS) that never looks back.

What is lost is the guarantee that made label-setting fast. Settle-on-pop meant each node was expanded at most once; with reopening, a node's g can be corrected many times, each correction re-queueing its descendants, and on adversarial graphs the number of reopenings grows exponentially. Correctness returns; the runtime bound does not.

The same trade reappears in informed search: A* with an inconsistent heuristic faces exactly this choice — forbid reopening and accept suboptimal answers, or allow it and give up the expansion bound. Recognising 'this is the reopening trade' inside a new algorithm is most of what this concept is for.

Reopening, mechanically

1. Cheaper path appearsA relaxation finds a g below the best recorded for a node already popped.
2. Re-queue the nodeRecord the better g and push the node back on the frontier — settled is now provisional.
3. Correct downstreamWhen it re-pops, its successors are re-relaxed, and corrections cascade.

4Bellman–Ford: pay for generality

Bellman–Ford abandons cleverness for coverage: relax every edge, V − 1 times over. After pass k, every shortest path that uses at most k edges is correct; and no shortest path needs more than V − 1 edges unless a negative cycle exists, so the table is exact when the passes finish. No ordering, no queue, no assumption about signs.

The bill is the pass structure itself — O(V·E) against Dijkstra's roughly (V + E) \log V — and at sizes routine for planners the gap is not a constant factor; it is the difference between interactive and overnight.

The V-th pass is a free diagnostic: if any edge still relaxes, some cycle sums negative — and then 'shortest path' is not expensive, it is undefined, because another lap always improves. The classic real instance is currency arbitrage: price each conversion at −log(rate) and a negative cycle is exactly a sequence of trades that multiplies to more than 1.

Figure. A cycle whose edges sum to −1: every lap around it lowers the total, so no finite shortest path through it exists. Bellman–Ford flags exactly this — an edge that still relaxes on the V-th pass.

5Negative costs in practice

Negative edges are rarer than they look and realer than beginners assume. The genuine sources: recovered energy (regenerative braking), rebates and subsidised legs in pricing problems, reward terms folded into a cost, and log-space products — a conversion rate above 1 prices below 0. The first response to a negative edge should always be to ask whether the model means it.

When it is meant, resist the folk repair: adding a big constant to every edge to make everything positive. The shift is not harmless, because routes absorb it in proportion to their edge count — a three-edge route gains three units of shift while a one-edge route gains one — and the ordering of totals can flip. The worked example on this concept flips one.

The principled version of the same instinct exists and is worth knowing by name: Johnson's reweighting adds a potential per node, pricing each edge as w + \phi(u) - \phi(v). The potentials telescope along any route, so every complete S-to-G total moves by the same \phi(S) - \phi(G): orderings survive, and negativity can be removed. That reweighting is the algebra behind A*'s heuristic in the informed-search lesson.

Figure. The same two routes before and after adding 1 to every edge: X wins at 3 against 4, then loses at 6 against 5. Three edges absorbed three units of shift; one edge absorbed one — the repair changed the answer.