Bellman-Ford Algorithm

Bellman-Ford solves single-source shortest paths even when some edge weights are negative. It is slower than Dijkstra — O(V·E) vs O((V+E) log V) — but it works correctly in the presence of negative weights and can detect negative cycles (cycles whose total weight is less than zero), which make the problem unsolvable.

The Relaxation Idea

A shortest path in a graph with V vertices visits at most V-1 edges. Bellman-Ford relaxes every edge V-1 times. After each round, any vertex reachable via a path of at most k edges has its correct distance if k rounds have completed.

// edges: Array<[from, to, weight]>
function bellmanFord(numVertices, edges, source) {
  const dist = new Array(numVertices).fill(Infinity);
  const prev = new Array(numVertices).fill(null);
  dist[source] = 0;

  // V-1 relaxation rounds
  for (let round = 0; round < numVertices - 1; round++) {
    let updated = false;
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        prev[v] = u;
        updated = true;
      }
    }
    if (!updated) break; // early exit if no updates
  }

  // Extra round: detect negative cycles
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      throw new Error("Graph contains a negative cycle");
    }
  }

  return { dist, prev };
}

// Graph with a negative edge: 0→1 (4), 0→2 (5), 1→3 (-3), 2→1 (2), 3→2 (1)
const edges = [
  [0, 1, 4],
  [0, 2, 5],
  [1, 3, -3],
  [2, 1, 2],
  [3, 2, 1],
];
const { dist } = bellmanFord(4, edges, 0);
console.log(dist); // [0, 4, 2, 1]

Negative Cycle Detection

If a distance can still be reduced after V-1 rounds, a negative cycle exists on some path from the source. The extra check on line 22 catches this condition. If no negative cycle is present, all distances are final after V-1 rounds.

Bellman-Ford vs Dijkstra

Use Bellman-Ford when edge weights can be negative or you need to confirm there are no negative cycles. Prefer Dijkstra in all other cases.

Up Next

Shift from shortest paths to spanning trees — Prim’s algorithm builds the minimum spanning tree by greedily growing from a seed vertex.