Shortest Path

Bellman-Ford

Relax ALL edges V−1 times. In each round, for every edge (u,v), if dist[u] + weight < dist[v], update dist[v]. After V−1 rounds, all shortest paths are found. Can detect negative cycles: if any edge can still be relaxed, a negative cycle exists.

O(V * E)

O(V)

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

Bellman-Ford from node 0. Edges: 0→1(4), 0→2(5), 1→2(-3)

∞

Round0

1/4

Code

Java

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

1Relax ALL edges V-1 times

2Can handle negative edge weights (unlike Dijkstra)

3If a Vth relaxation improves any distance, there's a negative cycle

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.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

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

When should I choose Bellman-Ford over Dijkstra?

Choose it when edges can be negative, or when you need to bound the number of edges in a path — limiting the relaxation rounds to k naturally answers 'cheapest path using at most k edges', as in Cheapest Flights Within K Stops. For non-negative weights with no edge-count constraint, Dijkstra is faster.

Why exactly V−1 rounds of relaxation?

A simple path visits each vertex at most once, so it contains at most V−1 edges. Each round extends correctness by at least one edge along every shortest path, so after V−1 rounds every simple shortest path has been fully relaxed. More rounds only matter if a negative cycle exists.

What is the pitfall when limiting rounds for the K-stops variant?

Within one round, updates must be based on the previous round's distances, or a single round could chain multiple edges together and use more stops than allowed. Copy the distance array at the start of each round and relax against the copy.