Bellman-Ford — Graph Algorithms

Overview

What this concept solves

Bellman-Ford answers the same question as Dijkstra — shortest paths from one source — but it works when edges can be negative. It pays for that with speed: O(V · E) instead of O((V + E) log V). The algorithm isn't greedy, it's patient: it relaxes every edge in the graph, V-1 times.

The intuition is shortest paths in a graph with V nodes contain at most V-1 edges (any longer and they'd have to revisit a node — a cycle). After one full pass over every edge, every node 1 edge away from the source has its true distance. After two passes, every node ≤ 2 edges away does. After V-1 passes, every reachable node is settled — and if a V-th pass would still improve some distance, the graph contains a negative cycle.

That last property — detecting negative cycles — is what makes Bellman-Ford the go-to algorithm for currency-arbitrage detection, financial flow analysis, and distance-vector routing protocols like the old RIP. You don't reach for Bellman-Ford for speed; you reach for it when negative edges or cycle detection are on the menu.

Mechanics

How it works

The algorithm in four lines

Give every node a distance estimate. The start gets 0, everyone else gets ∞.
Repeat V-1 times: for every edge (u, v, w), if dist[u] + w < dist[v], update dist[v]. (This is the same 'relax' step as Dijkstra.)
Do one more pass — the V-th. If any distance still improves, a negative cycle is reachable from the source.
Otherwise, dist holds the correct shortest distances.

Why V-1 passes are enough

Any shortest path has at most V-1 edges; with V nodes, any longer walk revisits a vertex and is either redundant (in a non-negative cycle) or worse than its acyclic version.
After pass k, every shortest path that uses ≤ k edges has been correctly computed — because at some point during pass k, the right edges along that path got relaxed in the right order.
After V-1 passes, every shortest path has been found. If a V-th pass still improves a distance, it's because there's a cycle that lowers the cost every time you go round — a negative cycle.

Why Dijkstra is faster

Dijkstra commits to one node per outer iteration — V outer iterations, each one log V work for the heap. Bellman-Ford has V-1 outer passes, each relaxing all E edges. The reason Dijkstra can do that — the cut-property argument — requires every edge ≥ 0. Bellman-Ford doesn't need that assumption, so it pays the V × E cost.

Negative cycle ≠ negative edge

A graph can have negative edges and still have well-defined shortest paths — as long as no cycle has a negative total weight. Bellman-Ford handles negative edges correctly; it only fails when a negative cycle is reachable from the source, in which case shortest paths are undefined (you could walk the cycle infinitely and drive the cost to -∞).

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Bellman-Ford

About this simulation

Five nodes, edges that include a negative weight. Press Play to watch Bellman-Ford relax every edge in every pass — V-1 passes total. Step / Back walk one edge-relaxation at a time. Try neg-cycle loads a graph with a negative cycle so the algorithm correctly flags it on the V-th pass.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through V-1 passes

Press Play. Watch the pass counter increment as every edge gets relaxed once per pass. Note how distances ratchet downward as the algorithm discovers shorter paths — particularly when a negative edge gets relaxed and propagates the improvement.

try 02

Step through one edge-relaxation at a time

Hit Step to relax the next edge in the current pass. Look at the Updated counter — early passes update many distances; later passes update fewer. If a pass updates nothing, the algorithm could safely stop early (and the optimised form does).

try 03

Try neg-cycle to see detection in action

Press Try neg-cycle to load a graph with a cycle whose edge weights sum to a negative number. Watch the algorithm complete V-1 passes normally, then on the V-th pass an edge still improves a distance — the prototype shows the cycle detected badge and halts. That extra pass is the entire negative-cycle test.

try 04

Compare convergence with Dijkstra

Open Dijkstra in another window with the same graph (minus the negative edge). Notice: Dijkstra settles each node exactly once and is done in V iterations. Bellman-Ford has to relax every edge V-1 times — even on graphs where Dijkstra would work. That's the cost of supporting negatives.

In practice

When to use it — and what you give up

When it's the right tool

Negative edge weights — the only classical SSSP algorithm that handles them correctly (with cycle detection).
Detecting negative cycles — currency arbitrage (FX rate logs encoded as -log(rate)); financial flow analysis; constraint solvers.
Distance-vector routing protocols — RIP and (informally) BGP both descend from Bellman-Ford: each router relaxes distance vectors from its neighbours.
Constraint systems — 'this difference must be ≤ that one' constraints encode as edges; Bellman-Ford either finds a feasible solution or proves the constraints are unsatisfiable (negative cycle).
As a building block — Johnson's all-pairs algorithm runs Bellman-Ford once to reweight the graph, then runs Dijkstra V times. Best of both worlds.

When to reach for something else

Non-negative weights — use Dijkstra. Same answer, much faster: O((V + E) log V) beats O(V · E) for sparse graphs.
All pairs needed — use Floyd-Warshall for small dense graphs (O(V³) is one big nested loop), or Johnson's for sparse graphs.
No weights — use BFS. It's even faster: O(V + E), no relaxation, no priority queue.

Pros

Handles negative edges — the only standard SSSP algorithm that does.
Detects negative cycles — for free, on a single extra pass.
Simple — two nested loops, no priority queue, no heap.
Distributed-friendly — each node only needs to know its neighbours, which is why distance-vector routing protocols are built on it.
Predictable — V-1 passes regardless of the graph shape; no worst-case blow-ups.

Cons

O(V · E) — much slower than Dijkstra on non-negative graphs.
Doesn't use heaps — and can't easily benefit from the 'process closest first' optimisation; that's what Dijkstra is for.
Slow convergence in distance-vector routing — the 'count to infinity' problem; protocols use poison reverse and split horizon as workarounds.
No early termination — must do V-1 passes even if shortest paths stabilise in one. (Some implementations check for 'no relaxations this pass' and exit early.)

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

bellman-ford.ts

// Bellman-Ford — single-source shortest paths.
// Handles negative edges; detects negative cycles.
type Edge = { from: string; to: string; w: number };

function bellmanFord(
  nodes: string[],
  edges: Edge[],
  start: string,
): Map<string, number> {
  const dist = new Map<string, number>();
  for (const u of nodes) dist.set(u, Infinity);
  dist.set(start, 0);

  // V-1 passes — every shortest path is found by the V-1'th pass.
  for (let i = 0; i < nodes.length - 1; i++) {
    let updated = false;
    for (const { from, to, w } of edges) {
      const nd = (dist.get(from) ?? Infinity) + w;
      if (nd < (dist.get(to) ?? Infinity)) {
        dist.set(to, nd);
        updated = true;
      }
    }
    if (!updated) break;        // optimisation: settled early
  }

  // V-th pass: any further improvement means a reachable negative cycle.
  for (const { from, to, w } of edges) {
    if ((dist.get(from) ?? Infinity) + w < (dist.get(to) ?? Infinity)) {
      throw new Error("graph contains a negative cycle reachable from start");
    }
  }
  return dist;
}

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why does Bellman-Ford run for exactly V-1 passes?

question 02 / 03

On Bellman-Ford's V-th (extra) pass, an edge can still be relaxed. What does this mean?

question 03 / 03

Why is Bellman-Ford O(V · E) while Dijkstra is O((V + E) log V)?

0/3 answered