Skip to main content

Bellman-Ford and Negative Edges

What This Concept Is​

Bellman-Ford solves single-source shortest paths on a directed graph with real-valued edge weights, including negative ones, and also decides whether a negative cycle is reachable from the source.

for each v in V: dist[v] := +infinity
dist[s] := 0
repeat |V| - 1 times:
    for each edge (u, v, w) in E:
        if dist[u] + w < dist[v]:
            dist[v] := dist[u] + w
            parent[v] := u
for each edge (u, v, w) in E:
    if dist[u] + w < dist[v]:
        report "negative cycle reachable from s"

Each pass relaxes every edge once. After k passes, dist[v] is the shortest path weight over paths of at most k edges. After |V| - 1 passes, shortest paths (if they exist) are found, since any shortest simple path has at most |V| - 1 edges. A further improving relaxation in an extra pass proves a negative cycle.

Total time: O(|V| * |E|).

Dijkstra vs Bellman-Ford in one line: Dijkstra is greedy (pick min and finalize); Bellman-Ford is iterative DP (relax every edge many times). The cost of generality over nonnegative weights is the |V| factor.

Why It Matters Here​

Bellman-Ford is the go-to algorithm whenever weights can be negative:

  • Currency arbitrage detection. Take w(u, v) = -log(rate(u, v)). A negative cycle means compounding trades around the loop multiply balances above 1 - arbitrage.
  • Shortest path with penalties / rebates. Transfer systems where some legs pay you.
  • Difference constraints (CLRS 22.4). Systems of inequalities x_j - x_i <= w_{ij} reduce to shortest paths in a constraint graph; Bellman-Ford decides feasibility.
  • Johnson's algorithm. Runs Bellman-Ford once to reweight a sparse graph into nonnegative weights, then Dijkstra from each vertex for APSP.

It is slower than Dijkstra but strictly more general. The slowdown is the price of handling negative edges.

Concrete Example​

Graph with a negative edge but no negative cycle:

Bellman-Ford from s, relaxation table (one legal iteration order):

passdist[s]dist[a]dist[b]dist[c]dist[d]
init0infinfinfinf
106724
2027-24
3027-24
4027-24

Stabilized at dist = {s:0, a:2, b:7, c:-2, d:4}. A fifth pass produces no improvement, so "no negative cycle reachable from s."

If the edge d -(-2)-> a were d -(-5)-> a, the cycle a -> c -> ... -> d -> a would total -4 + 9 + (-5) = 0 or negative (depending on chosen cycle vertices), and the extra pass would still produce improvements - negative cycle detected.

Common Confusion / Misconceptions​

  • "Negative edges are fine, negative cycles are the only problem for Dijkstra." The second half is false. Dijkstra still fails with only negative edges and no negative cycle, because its finalization invariant is broken the moment a finalized vertex can be relaxed.
  • "Bellman-Ford detects any negative cycle." It detects negative cycles reachable from the source. Negative cycles disconnected from s are invisible to a single run. To detect any negative cycle, add a super-source with zero-weight edges to every vertex and run Bellman-Ford from it.
  • "Early exit breaks correctness." It does not. If a whole pass produces no relaxation, the array has converged; you can terminate. This is standard.
  • "SPFA is faster." SPFA (Shortest Path Faster Algorithm) is a queue-based variant, often fast on random graphs, but the worst-case running time is still O(|V| |E|) and adversarial inputs can force |V|^2 |E|. Do not rely on it for worst-case bounds.

How To Use It​

Baseline Bellman-Ford:

  1. initialize dist[s] := 0, everything else +infinity
  2. loop |V| - 1 times, relaxing every edge
  3. do one more pass; if any edge still relaxes, a negative cycle is reachable from s

Optimizations:

  • Early exit. If an entire pass produces no relaxation, stop - shortest paths have converged.
  • SPFA. Keep a queue of vertices whose dist just decreased; pop one, relax its out-edges, push any neighbor whose dist decreased (if not already in the queue). Works well on random graphs.
  • Super-source trick. Add vertex s' with zero-weight edges to all vertices; run from s' to detect any negative cycle in the graph.
  • Cycle extraction. When a relaxation in the |V|-th pass reveals a negative cycle on edge (u, v), walk v's parent[] chain backward |V| steps to reach a vertex inside the cycle, then follow parent[] until it repeats.

Transfer / Where This Shows Up Later​

  • S3 (systems). Distance-vector routing (RIP) is Bellman-Ford in distributed form. Each router iteratively relaxes its best-known distances based on neighbor advertisements.
  • S4 (compilers). Feasibility of difference-constraint systems arising from instruction scheduling and live-range overlaps reduces to Bellman-Ford on the constraint graph.
  • S5 (OS). Priority-inheritance with deadline feasibility checks can encode as difference constraints solved by Bellman-Ford.
  • S6 (databases). Query engines that model cost rebates (pushed-down predicate savings) need negative-weight-tolerant shortest path.
  • S7 (DDD). Cost-of-change propagation with credits uses Bellman-Ford-style relaxation.
  • S8 (distributed). BGP path-selection is inspired by distance-vector, though with policy overlays; historically exhibits the "count-to-infinity" problem BGP mitigates with path vectors.

Back-link to concept 10 (Dijkstra) for why negative edges break the greedy-finalization proof, and forward to Johnson's algorithm (CLRS 23.3) for how Bellman-Ford enables APSP on sparse graphs with negative weights.

Check Yourself​

  1. Why are exactly |V| - 1 passes sufficient when no negative cycle is present?
  2. Why does the |V|-th pass serving as a "tripwire" work as a negative-cycle detector?
  3. Why does Dijkstra fail with negative edges even without a negative cycle?
  4. How would you recover a negative cycle (not just detect it) when one is detected?
  5. What is the super-source trick, and why does it detect negative cycles disconnected from the original source?
  6. Why is SPFA worst-case no better than Bellman-Ford despite being "faster in practice"?

Mini Drill or Application​

On the graph

1 -(4)-> 2
1 -(5)-> 3
2 -(-3)-> 4
3 -(6)-> 4
4 -(-2)-> 2

run Bellman-Ford from vertex 1. Show dist[] after each of the first three passes and identify the negative cycle if one exists.

Implementation drill.

  1. Implement Bellman-Ford with the early-exit optimization.
  2. Build a currency graph from exchange rates using w(u, v) = -log(rate(u, v)); verify that a negative cycle witnesses arbitrage and reconstruct it.
  3. Add negative-cycle extraction that prints the cycle edges.
  4. Implement a super-source wrapper that detects any negative cycle in the graph.
  5. As a stretch goal, implement Johnson's algorithm: Bellman-Ford for reweighting + Dijkstra from each vertex; verify APSP correctness against Floyd-Warshall on a small graph.

Read This Only If Stuck​