When do you accept Bellman-Ford's O(V*E) instead of removing negative rebate edges to use Dijkstra?

## Reframe: this is an assumptions question, not a speed question A greedy shortest-path algorithm works by settling the closest unfinished vertex and never reconsidering it. That is sound only because, with all weights non-negative, no route through a farther vertex can come back cheaper. Put one negative edge in and the argument collapses: a vertex can be finalised, then a later rebate edge offers a cheaper way in, and the answer is silently wrong. So the two algorithms are not two speeds for one problem — one of them has a precondition your graph violates. "Just slower" is the wrong-answer this question is aimed at, and the correction is that Bellman-Ford also **certifies** something: its extra pass proves no loop of edges can be walked for unbounded gain, which on a pricing graph is a statement about whether your tariff rules can be gamed. ## Step one: interrogate the negative edges Before optimising, ask what a negative weight encodes. A volume rebate, a backhaul credit, a promotional subsidy on a leg — these are real money the business receives, and a route planner that ignores them will systematically pick the wrong carrier. If instead the negative values are an artefact (a sign error, a modelling shortcut, a discount that is actually capped and non-compounding), fixing the data is the right answer and the algorithm question dissolves. Only when the negatives are real does the tradeoff begin. ## Step two: the fixes that quietly change the answer - **Add a constant `C` to every edge so nothing is negative.** A route with `k` edges gains `k*C`, so you have added a per-hop tax. A five-leg route that was cheapest now loses to a two-leg route that is genuinely more expensive. This is the single most common wrong proposal in this discussion. - **Clamp negatives to zero.** You deleted the rebate. Correct algorithm, different cost function, wrong route. - **Take absolute values.** A credit became a charge; routes that should be attractive are now the ones you avoid. ## Step three: the transform that does not Compute a potential `h(v)` for every vertex with one Bellman-Ford run from a virtual source joined to every vertex by a zero-weight edge, then reweight every edge as `w'(u,v) = w(u,v) + h(u) - h(v)`. Two things hold. It is non-negative, because `h` satisfies the triangle inequality `h(v) <= h(u) + w(u,v)`. And it preserves shortest routes exactly: summing along any route from `s` to `t` telescopes, so every route's weight shifts by the same `h(s) - h(t)`, leaving the ranking untouched. Now a greedy algorithm with a min-priority queue is legal, at `O((V+E) log V)` per query. This reweighting is the core of the classical Johnson construction, and Bellman-Ford is the subroutine that makes it possible — a sharp answer to the "just slower" jab, since the fast path *depends on* the slow algorithm. Its costs are organisational, not just asymptotic: something must recompute `h` whenever the tariff table changes, something must invalidate caches when it does, and the team has to understand a potential function to debug a routing complaint. If the rates change more often than you query, the precompute never amortises and you have bought complexity for nothing. ## Step four: the numbers you actually decide on Write the budget down. With `V = 200,000` and `E = 3,000,000`, `V*E` is about `6 * 10^11` relaxations — hours, not an online request. With `V = 400` and `E = 5,000`, it is two million relaxations, i.e. nothing, and any further engineering is waste. The middle is where judgment lives: how many queries per run, how often the weights change, is the answer needed in a request or in a nightly file, and what happens at ten times today's graph — `V*E` grows roughly with the square of scale on a graph of fixed density, so a three-second job becomes a five-minute one. ## Step five: the structure you may already have If the network is acyclic — pricing stages, a time-expanded schedule where every edge moves forward in time — relax edges in topological order and you get `O(V+E)` with negative weights fully allowed and no passes at all. Checking for that shape before arguing about pass counts is the cheapest win on the table. ## What to say out loud Name the precondition, not the constant factor: the greedy algorithm is disqualified here, and the reweighting trick that re-qualifies it runs Bellman-Ford anyway. Then decide on the query pattern and the change rate of the weights, and keep the negative-cycle check permanently in the batch job as an invariant on the pricing rules — the day a rebate combination becomes loopable, you want an alert rather than a route planner quietly recommending an infinite tour.