Bellman-Ford Algorithm

Bellman-Ford finds the shortest path from a single source to all vertices in a weighted directed graph — even when some edge weights are negative. It also detects negative cycles, which Dijkstra cannot do.

The trade-off: it is slower than Dijkstra, running in O(V·E) time.

Core Idea — Relaxation Passes

The algorithm works by repeatedly "relaxing" every edge. Relaxing an edge (u, v, w) means:

"If the best known way to reach u, plus the edge weight w, is better than the current best way to reach v — update v's distance."

A shortest path with at most k edges can be found after k relaxation passes. Since the longest possible shortest path in a graph with V vertices uses at most V−1 edges (a path visiting each vertex once), V−1 passes are always sufficient.

If distances still improve on a V-th pass, the graph contains a negative cycle reachable from the source — a cycle whose total weight is negative. Following it indefinitely would give −∞ cost, so no well-defined shortest path exists.

Full Implementation

// vertices: number of vertices (0-indexed)
// edges: array of [u, v, weight]
// start: source vertex
function bellmanFord(vertices, edges, start) {
  const dist = new Array(vertices).fill(Infinity);
  dist[start] = 0;

  // V-1 relaxation passes
  for (let pass = 0; pass < vertices - 1; pass++) {
    let updated = false; // early exit optimisation
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        updated = true;
      }
    }
    if (!updated) break; // no updates this pass → already converged
  }

  // V-th pass: detect negative cycles
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // negative cycle reachable from start
    }
  }
  return dist;
}

// Example
const edges = [
  [0, 1, -1],
  [0, 2,  4],
  [1, 2,  3],
  [1, 3,  2],
  [1, 4,  2],
  [3, 2,  5],
  [3, 1,  1],
  [4, 3, -3],
];
console.log(bellmanFord(5, edges, 0));
// [0, -1, 2, -2, 1]
// Shortest paths: 0→0=0, 0→1=-1, 0→1→2=2, 0→1→4→3=-2, 0→1→4=1

Note

Time: O(V·E). Space: O(V). The early-exit optimisation (break when no updates occurred in a pass) can significantly speed up the algorithm on sparse graphs.

Detecting Negative Cycles

The V-th relaxation pass is the detection mechanism. If any distance improves, there is a path from the source through a negative cycle to that vertex.

To find all vertices affected by negative cycles (not just those reachable from the source), propagate -Infinity through the graph in a BFS/DFS after the V-th pass.

function bellmanFordWithCycles(vertices, edges, start) {
  const dist = new Array(vertices).fill(Infinity);
  dist[start] = 0;

  for (let pass = 0; pass < vertices - 1; pass++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Mark vertices reachable via negative cycles as -Infinity
  for (let pass = 0; pass < vertices - 1; pass++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = -Infinity; // negative cycle influence
      }
    }
  }
  return dist;
}

// -Infinity in the result means that vertex is reachable with cost → -∞

Path Reconstruction

function bellmanFordPath(vertices, edges, start, end) {
  const dist = new Array(vertices).fill(Infinity);
  const prev = new Array(vertices).fill(-1);
  dist[start] = 0;

  for (let pass = 0; pass < vertices - 1; pass++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        prev[v] = u;
      }
    }
  }

  if (dist[end] === Infinity) return { dist: Infinity, path: [] };

  // Trace back the path
  const path = [];
  let cur = end;
  while (cur !== -1) { path.unshift(cur); cur = prev[cur]; }
  return { dist: dist[end], path };
}

const edges2 = [[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]];
console.log(bellmanFordPath(5, edges2, 0, 3));
// { dist: -2, path: [0, 1, 4, 3] }

SPFA — Shortest Path Faster Algorithm

SPFA is a queue-based optimisation of Bellman-Ford. Instead of relaxing all edges every pass, only relax edges from vertices whose distances were updated in the previous round. This reduces practical running time to roughly O(kE) where k is the average number of times a vertex is added to the queue — often close to O(E) in practice.

However, SPFA is still O(V·E) in the worst case (adversarial graphs) and has fallen out of favour in competitive programming because it can be hacked. Use Dijkstra when possible.

function spfa(vertices, edges, start) {
  // Build adjacency list for SPFA
  const graph = Array.from({ length: vertices }, () => []);
  for (const [u, v, w] of edges) graph[u].push([v, w]);

  const dist    = new Array(vertices).fill(Infinity);
  const inQueue = new Array(vertices).fill(false);
  const count   = new Array(vertices).fill(0); // relaxation count per vertex
  dist[start] = 0;

  const queue = [start];
  inQueue[start] = true;

  while (queue.length > 0) {
    const u = queue.shift();
    inQueue[u] = false;

    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        count[v]++;
        if (count[v] >= vertices) return null; // negative cycle
        if (!inQueue[v]) {
          queue.push(v);
          inQueue[v] = true;
        }
      }
    }
  }
  return dist;
}

Warning

SPFA is vulnerable to adversarial test cases that force O(V·E) behaviour. In competitive programming, prefer Dijkstra for non-negative graphs and standard Bellman-Ford for negative graphs.

Problem — Cheapest Flights Within K Stops (LeetCode 787)

Find the cheapest price from src to dst using at most K stops (K+1 edges).

Bellman-Ford is a perfect fit: each pass i computes the cheapest cost using at most i edges. After exactly K+1 passes, we have the answer. Unlike Dijkstra, we don't need extra state to track the number of stops.

Important: use a copy of the dist array at the start of each pass to avoid using edges relaxed within the same pass (which would count a path using more edges than allowed).

function findCheapestPrice(n, flights, src, dst, k) {
  // k stops = k+1 edges maximum
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  for (let i = 0; i <= k; i++) {
    // Snapshot dist to avoid intra-pass relaxation
    const temp = [...dist];
    for (const [u, v, price] of flights) {
      if (dist[u] !== Infinity && dist[u] + price < temp[v]) {
        temp[v] = dist[u] + price;
      }
    }
    dist.splice(0, n, ...temp); // update dist with temp
  }
  return dist[dst] === Infinity ? -1 : dist[dst];
}

console.log(findCheapestPrice(4,
  [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],
  0, 3, 1));
// 700  — take flight 0→1 (100) + 1→3 (600) = 700
// Only 1 stop (k=1), so 0→1→2→3 (3 edges, 2 stops) is not allowed

Tip

The "snapshot" approach is the key to the strict K-stops constraint. Without it, a single Bellman-Ford pass can chain multiple edges from the same iteration, effectively using more hops than allowed.

Dijkstra vs Bellman-Ford

Property	Dijkstra	Bellman-Ford
Negative weights	No	Yes
Negative cycle detection	No	Yes (V-th pass)
Time complexity	O((V+E) log V)	O(V·E)
Space complexity	O(V)	O(V)
Approach	Greedy (min-heap)	Dynamic programming (relaxation)
K-hop constraint	Needs state augmentation	Natural — one pass = one hop

Practice Problems

LeetCode 787 — Cheapest Flights Within K Stops
LeetCode 743 — Network Delay Time (compare with Dijkstra)
LeetCode 1334 — Find the City With the Smallest Number of Neighbors at a Threshold Distance
LeetCode 2093 — Minimum Cost to Reach City With Discounts
LeetCode 1928 — Minimum Cost to Reach Destination in Time