Ankit Kashyap

Bellman Ford

Single source shortest path Ref: https://www.youtube.com/watch?v=FtN3BYH2Zes

Bellman-Ford finds the shortest path from a source node to every other node in a weighted graph. Unlike Dijkstra, it can handle negative edge weights.

Key

Relax all edges n-1 times (n = number of nodes in graph) Relaxation formula - distance d[v] = min(d[v], d[u] + c[u,v])

Core Idea

Suppose the shortest path can have at most V - 1 edges.

If we repeatedly relax every edge:

dist[v] = min(dist[v], dist[u] + weight)

then after:

  • 1st pass → shortest paths using ≤ 1 edge
  • 2nd pass → shortest paths using ≤ 2 edges
  • …
  • (V-1)th pass → all shortest paths found

Why V - 1 Times?

A shortest path never needs more than V - 1 edges.

If a path contains V or more edges, some vertex must repeat, creating a cycle.

dist = [∞, ∞, ..., ∞];
dist[src] = 0;
 
for (let i = 0; i < V - 1; i++) {
    for (const [u, v, w] of edges) {
        dist[v] = Math.min(dist[v], dist[u] + w);
    }
}

Negative Cycle Detection

Run one more relaxation pass.

If any distance still improves:

dist[v] > dist[u] + w

then a negative cycle exists.

This is Bellman-Ford’s biggest advantage over Dijkstra.

We use a temporary array because each Bellman-Ford iteration should represent paths using one additional edge. The temp array prevents newly relaxed distances from being reused in the same iteration, ensuring that after i iterations we have only considered paths with at most i edges.

time: O(V × E) space: O(V)

var findCheapestPrice = function (n, flights, src, dst, k) {
  const INF = Infinity;
 
  // prices[i] = cheapest cost to reach city i using current allowed edges
  let prices = new Array(n).fill(INF);
  prices[src] = 0;
 
  // k stops means at most k + 1 flights/edges
  for (let i = 0; i <= k; i++) {
    const temp = [...prices];
 
    for (const [from, to, cost] of flights) {
      if (prices[from] === INF) continue;
 
      if (prices[from] + cost < temp[to]) {
        temp[to] = prices[from] + cost;
      }
    }
 
    prices = temp;
  }
 
  return prices[dst] === INF ? -1 : prices[dst];
};

When to Think of Bellman-Ford

  • Graph has negative weights
  • Need negative cycle detection
  • Need shortest path with a limited number of edges/stops (like LeetCode 787 Cheapest Flights Within K Stops)

For the cheapest flight path problem, we modify Bellman-Ford slightly:

  • Instead of V-1 iterations,
  • Perform only k+1 iterations,
  • Use a temporary copy of distances each round,

Backlinks