Bellman-Ford algorithm

Overview

Bellman-Ford computes single-source shortest paths even when some edges have negative weights. It relaxes every edge V - 1 times. After round k, all shortest paths that use at most k edges are correct, and since a simple path has at most V - 1 edges, V - 1 rounds are enough.

A V-th round detects negative cycles: if any distance still improves, a cycle with negative total weight is reachable and shortest paths are undefined. Its O(V x E) cost is slower than Dijkstra, but the 'at most k edges' property directly solves problems with a limit on stops.

When to use it

• Edge weights can be negative.
• You must detect negative cycles (arbitrage, inconsistent constraints).
• Shortest path with at most K edges or stops.
• Distributed settings where each node only knows its neighbors (distance-vector routing).

Problem patterns it solves

Where it is used in real software

Key terms

Relaxation round

One pass over every edge trying dist[u] + w < dist[v].

V - 1 rounds

Enough for any simple shortest path.

Negative cycle

A cycle whose total weight is negative; distances can decrease forever.

SPFA

Queue-based optimization that only relaxes edges from nodes that changed.

How it works, step by step

1. 1
   Initialize

   dist[source] = 0; all others Infinity.

2. 2
   Repeat V - 1 times

   For every edge (u, v, w): if dist[u] + w < dist[v], update dist[v].

3. 3
   Stop early

   If a whole round changes nothing, distances are final.

4. 4
   Check for negative cycles

   Run one more round; any improvement means a reachable negative cycle.

5. 5
   For K-stop limits

   Run exactly K + 1 rounds and relax from a copy of the previous round's distances.

Negative edge handled correctly

Edges: S->A 4, S->B 5, B->A -3, A->C 2

The best path to A goes through B even though S->B is longer, thanks to the -3 edge. Dijkstra would have finalized A = 4 too early.

Implementation

1function bellmanFord(n, edges, source) {2  const dist = new Array(n).fill(Infinity);3  dist[source] = 0;4  for (let round = 0; round < n - 1; round++) {5    let changed = false;6    for (const [u, v, w] of edges) {7      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {8        dist[v] = dist[u] + w;9        changed = true;10      }11    }12    if (!changed) break;13  }14  for (const [u, v, w] of edges) {15    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {16      return { dist, negativeCycle: true };17    }18  }19  return { dist, negativeCycle: false };20}21 22// 787. Cheapest Flights Within K Stops: exactly k + 1 edge rounds23function findCheapestPrice(n, flights, src, dst, k) {24  let dist = new Array(n).fill(Infinity);25  dist[src] = 0;26  for (let i = 0; i <= k; i++) {27    const next = dist.slice(); // use only last round's values28    for (const [u, v, price] of flights) {29      if (dist[u] !== Infinity && dist[u] + price < next[v]) next[v] = dist[u] + price;30    }31    dist = next;32  }33  return dist[dst] === Infinity ? -1 : dist[dst];34}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Updating dist in place for the K-stop variant.

  Fix: In-place updates can chain several edges in one round; copy the array each round.

• Adding to Infinity.

  Fix: Skip edges where dist[u] is Infinity (critical in Java with MAX_VALUE overflow).

• Reporting distances when a negative cycle exists.

  Fix: Distances reachable from the cycle are undefined; report the cycle.

Interview questions

Practice problems