Bellman-Ford

How Bellman-Ford works

The algorithm is brutally simple: relax every edge V-1 times. Relaxing an edge (u, v, w) means: if dist[u] + w < dist[v], set dist[v] = dist[u] + w.

After iteration k, every shortest path of at most k edges has the correct distance. Since any shortest path has at most V-1 edges (more edges would require a cycle, which can only lengthen the path under non-negative-cycle assumptions), V-1 iterations suffice.

The negative-cycle check is a free bonus: run one more iteration. If anything still changes, there's a negative cycle reachable from the source. The intuition: shortest paths must stabilize after V-1 iterations, so further changes mean some "distance" is decreasing without bound — that requires a negative cycle.

Negative cycle detection

Run V-1 iterations of edge relaxation. Then for the V-th iteration, scan every edge. If any edge (u, v, w) still satisfies dist[u] + w < dist[v], the graph has a negative-weight cycle reachable from the source — and there is no well-defined shortest path.

This is exactly how arbitrage detection works in finance. Treat each currency as a vertex; each pair of currencies has an exchange-rate edge. Take the negative logarithm of the rate as the edge weight, and a negative cycle now corresponds to a sequence of trades that multiply your money. Bellman-Ford finds these in O(V·E).

Bellman-Ford vs Dijkstra

	Bellman-Ford	Dijkstra
Time	O(V · E)	O((V + E) log V)
Edge weights	Any (positive, negative, zero)	Non-negative only
Detects negative cycles	Yes	No (silently wrong)
Approach	Relax every edge each round	Greedy: pick min-distance node, relax outgoing
Data structure	None — flat arrays	Min-priority queue (heap)
Goal-directed	No	No (use A* for that)
Code complexity	~10 lines	~25 lines (heap + stale check)
Best for	Graphs with negative weights, distance-vector routing	Non-negative weights, GPS, pathfinding

Use Dijkstra when you can — it's faster. Reach for Bellman-Ford only when the graph might have negative weights or you need negative-cycle detection.

When to use Bellman-Ford

• Currency arbitrage detection. Take -log(exchange rate) as the edge weight; a negative cycle is a profitable trade sequence.
• Distance-vector routing protocols (RIP). Routers exchange shortest-path estimates; Bellman-Ford's per-edge relaxation maps naturally to per-link updates. Modern networks have shifted to link-state (Dijkstra-based) protocols, but Bellman-Ford's distributed nature still has uses.
• Game and economic models with rebates / refunds. Negative edge weights model "this action gives you energy/money back." Dijkstra would silently mis-handle these.
• Detecting impossibility in pathfinding. If the question is "does a feasible path exist," running Bellman-Ford and checking for negative cycles tells you whether the cost can be made arbitrarily low — a sign of a broken model.

Pseudo-code

function bellmanFord(graph, source):
    dist = { v: infinity for v in vertices }
    prev = { v: null for v in vertices }
    dist[source] = 0

    # V-1 rounds of edge relaxation
    for i from 1 to V - 1:
        for each edge (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    # V-th round detects negative cycles
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            return "NEGATIVE_CYCLE"

    return dist, prev

JavaScript implementation

function bellmanFord(vertices, edges, source) {
  const dist = new Map();
  const prev = new Map();
  for (const v of vertices) {
    dist.set(v, Infinity);
    prev.set(v, null);
  }
  dist.set(source, 0);

  // V-1 rounds of relaxation
  for (let i = 0; i < vertices.length - 1; i++) {
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist.get(u) + w < dist.get(v)) {
        dist.set(v, dist.get(u) + w);
        prev.set(v, u);
        changed = true;
      }
    }
    if (!changed) break; // early termination — graph is stable
  }

  // V-th round: any further relaxation = negative cycle
  for (const [u, v, w] of edges) {
    if (dist.get(u) + w < dist.get(v)) {
      throw new Error('Negative-weight cycle detected');
    }
  }

  return { dist, prev };
}

The early-termination optimization (if (!changed) break) is huge in practice. Graphs that stabilize quickly — most real-world graphs do — finish in far fewer than V-1 rounds. The asymptotic bound stays O(V·E) but the constant factor improves dramatically.

Python implementation

from math import inf

def bellman_ford(vertices, edges, source):
    dist = {v: inf for v in vertices}
    prev = {v: None for v in vertices}
    dist[source] = 0

    # V-1 rounds
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed: break

    # Negative cycle check
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError('Negative-weight cycle')

    return dist, prev

Famous Bellman-Ford problems

Currency Arbitrage Detection

Given exchange rates between n currencies, detect a sequence of trades that produces profit. Construct a graph with vertex per currency and edge weight -log(rate) from currency A to B. A negative cycle in this graph is a profitable trade sequence — the negative logs sum to a negative number, so the original rates multiply to greater than 1. Run Bellman-Ford from any vertex; the V-th round flag indicates whether arbitrage exists.

Cheapest Flights Within K Stops

Bellman-Ford naturally handles "at most K edges" — just run K iterations instead of V-1. Each iteration extends paths by one edge; K iterations gives shortest paths using at most K edges. Use a snapshot of the previous iteration's dist to ensure each pass uses paths of exactly that length.

Common bugs and edge cases

• Forgetting the V-th round. Without it, you don't detect negative cycles — and silently return distances that are arbitrarily wrong (the algorithm reports finite distances even when no shortest path exists).
• Updating dist in place during a single round. Strictly, each round should be based on the previous round's dist values. Updating in place often still gives correct shortest distances faster, but it changes which paths are explored — and breaks the "shortest path with at most K edges" use case where you need a per-round snapshot.
• Using sentinel values that overflow. If dist[u] = Infinity and you compute dist[u] + w, you might overflow in fixed-precision languages. Skip relaxation when dist[u] = Infinity (it can't reach v anyway).
• Confusing reachable negative cycles with all negative cycles. Bellman-Ford detects negative cycles reachable from the source. A negative cycle in a disconnected component won't be flagged. To find all negative cycles, run Bellman-Ford from every vertex (or use Floyd-Warshall).
• Using Bellman-Ford when Dijkstra would work. Bellman-Ford is V-1 times slower. If you can prove all weights are non-negative, switch.