Bellman-Ford

How It Works

Bellman-Ford computes single-source shortest paths even when edges have negative weights. It performs V-1 rounds; in each round it scans every edge (u, v) and relaxes it: if dist[u] + weight < dist[v], update dist[v]. The key insight is that a shortest path in a graph without negative cycles uses at most V-1 edges, and round i guarantees all shortest paths of at most i edges are correct, so V-1 rounds suffice.

The cost is O(V·E), slower than Dijkstra's O(E log V), which is the price paid for handling negative weights without any greedy assumption. A bonus V-th pass detects negative cycles: if any edge can still be relaxed, some cycle has negative total weight and shortest distances are undefined for nodes it can reach. An early exit when a full pass makes no updates is a common practical optimization.

Step-by-Step Visualization

Code

static int[] bellmanFord(int[][] edges, int n, int start) {
  int[] dist = new int[n];
  Arrays.fill(dist, Integer.MAX_VALUE);
  dist[start] = 0;

  for (int i = 0; i < n - 1; i++) {
    for (int[] e : edges) {
      int u = e[0], v = e[1], w = e[2];
      if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Check for negative cycles
  for (int[] e : edges) {
    if (dist[e[0]] + e[2] < dist[e[1]]) return null; // Negative cycle!
  }
  return dist;
}

Tips & Gotchas

Practice Problems

• 1Cheapest Flights Within K Stops
• 2Network Delay Time
• 3Minimum Cost to Reach City With Discounts

About the Shortest Path Pattern

Find the minimum cost path between nodes. The right algorithm depends on the graph: unweighted → BFS, non-negative weights → Dijkstra, negative weights → Bellman-Ford, all-pairs → Floyd-Warshall.

Common Graphs Interview Problems

• Number of Islands
• Clone Graph
• Course Schedule
• Pacific Atlantic Water Flow
• Network Delay Time
• Minimum Spanning Tree
• Word Ladder

Frequently Asked Questions

Other Shortest Path Techniques