Bellman-Ford finds the shortest paths from one source to all vertices, even when edges have negative weights.

It can also detect:

Negative cycles reachable from the source.

Its main advantage:

Handles negative edges and detects reachable negative cycles, at the cost of O(V × E) time.

Focus on recognizing:

“Shortest path” + “negative edges” + “negative cycle detection” = Bellman-Ford

Mental Trigger

Initialize distances → Relax every edge V-1 times → Check once more for a possible improvement.

Why V - 1?

A shortest simple path can contain at most:

V - 1 edges

because a path containing V or more edges must repeat a vertex.

Pattern Table

1. Generic Java Bellman-Ford Template

Watch a full relaxation sweep — note the negative edge handled without complaint, and the extra cycle-check pass:

                        1
                        dist[] = {S:0, rest:∞}
                      
                        2
                        repeat V-1 times:
                      
                        3
                          for EVERY edge (u → v):
                      
                        4
                            if dist[u] + w < dist[v]:
                      
                        5
                              dist[v] = dist[u] + w
                      
                        6
                        # one extra pass detects negative cycles
                      

public int[] bellmanFord(int n, int[][] edges, int src) {
    int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];

    Arrays.fill(dist, INF);
    dist[src] = 0;

    // Relax all edges up to V - 1 times
    for (int i = 0; i < n - 1; i++) {
        boolean changed = false;

        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];

            // Ignore unreachable vertices
            if (dist[u] == INF) continue;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }

        // No improvement means shortest distances are finalized
        if (!changed) break;
    }

    // One more pass: detect reachable negative cycle
    for (int[] e : edges) {
        int u = e[0];
        int v = e[1];
        int w = e[2];

        if (dist[u] == INF) continue;

        if (dist[u] + w < dist[v]) {
            return new int[0]; // reachable negative cycle
        }
    }

    return dist;
}

def bellman_ford(n, edges, src):
    INF = float('inf')
    dist = [INF] * n

    dist[src] = 0

    # Relax all edges up to V - 1 times
    for _ in range(n - 1):
        changed = False

        for u, v, w in edges:
            # Ignore unreachable vertices
            if dist[u] == INF:
                continue

            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True

        # No improvement means distances are finalized
        if not changed:
            break

    # One more pass: detect reachable negative cycle
    for u, v, w in edges:
        if dist[u] == INF:
            continue

        if dist[u] + w < dist[v]:
            return []  # reachable negative cycle

    return dist

vector<int> bellmanFord(int n, vector<vector<int>>& edges, int src) {
    const int INF = INT_MAX;
    vector<int> dist(n, INF);

    dist[src] = 0;

    // Relax all edges up to V - 1 times
    for (int i = 0; i < n - 1; i++) {
        bool changed = false;

        for (auto& e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];

            // Ignore unreachable vertices
            if (dist[u] == INF) continue;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }

        // No improvement means distances are finalized
        if (!changed) break;
    }

    // One more pass: detect reachable negative cycle
    for (auto& e : edges) {
        int u = e[0];
        int v = e[1];
        int w = e[2];

        if (dist[u] == INF) continue;

        if (dist[u] + w < dist[v]) {
            return {}; // reachable negative cycle
        }
    }

    return dist;
}

function bellmanFord(n, edges, src) {
  const INF = Infinity;
  const dist = new Array(n).fill(INF);

  dist[src] = 0;

  // Relax all edges up to V - 1 times
  for (let i = 0; i < n - 1; i++) {
    let changed = false;

    for (const [u, v, w] of edges) {
      // Ignore unreachable vertices
      if (dist[u] === INF) continue;

      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }

    // No improvement means distances are finalized
    if (!changed) break;
  }

  // One more pass: detect reachable negative cycle
  for (const [u, v, w] of edges) {
    if (dist[u] === INF) continue;

    if (dist[u] + w < dist[v]) {
      return []; // reachable negative cycle
    }
  }

  return dist;
}

2. Core Operation: Relaxation

The most important operation is:

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

This means:

“Can I reach v more cheaply by going through u?”

For an edge:

u ----w----> v

we check:

dist[u] + w < dist[v]

If yes:

dist[v] = dist[u] + w

Bellman-Ford = repeatedly relax every edge.

3. Why V - 1 Passes?

Suppose the shortest path is:

A → B → C → D

It contains 3 edges.

After enough relaxation passes, the shortest distance can propagate through those edges.

A simple shortest path in a graph with V vertices can contain at most:

V - 1 edges

Therefore:

for (int i = 0; i < n - 1; i++)

is sufficient.

4. Negative Cycle Detection

After V - 1 relaxation rounds, perform one additional pass.

for (int[] e : edges) {
    if (dist[e[0]] == INF) continue;

    if (dist[e[0]] + e[2] < dist[e[1]]) {
        // Negative cycle reachable from source
    }
}

Why?

If a distance can still improve after V - 1 rounds, then the improvement must come from repeatedly traversing a cycle.

A reachable cycle with:

total weight < 0

allows the path cost to decrease indefinitely.

Example:

A --2--> B
B --(-5)--> C
C --1--> A

Cycle weight:

2 + (-5) + 1 = -2

Every time we traverse the cycle:

distance decreases by 2

Therefore there is no finite shortest path for vertices affected by that cycle.

Relax after V-1 rounds → reachable negative cycle exists.

5. Why Check INF?

This is essential:

if (dist[u] == INF) continue;

Suppose:

dist[u] = Integer.MAX_VALUE;

and:

w = -10;

Then:

dist[u] + w

can overflow because Java int arithmetic wraps around.

That can produce an incorrect negative number and create a fake shortest path.

Correct Pattern

if (dist[u] != INF && dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

6. Early Termination

Bellman-Ford does not always need all V-1 passes.

Track whether anything changed:

boolean changed = false;

When relaxing:

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
    changed = true;
}

After processing all edges:

if (!changed) break;

If no distance changed, another complete pass cannot improve the current solution.

No relaxation → shortest distances have stabilized.

7. Bellman-Ford vs Dijkstra

This is one of the most important recognition points.

Mental Trigger

Negative edge?
    ↓
Bellman-Ford

All weights non-negative?
    ↓
Dijkstra is usually faster

8. Example

Consider:

0 → 1 (4)
0 → 2 (5)
1 → 2 (-2)
2 → 3 (3)

Initial:

dist = [0, INF, INF, INF]

Relaxation eventually gives:

0 → 1 = 4
0 → 2 = 2      // 0 → 1 → 2
0 → 3 = 5      // 0 → 1 → 2 → 3

Final:

dist = [0, 4, 2, 5]

The negative edge is perfectly valid:

1 → 2 = -2

This is where Bellman-Ford is useful.

Pattern Evolution

Initialize dist[source] = 0
        ↓
Relax every edge
        ↓
Repeat V - 1 times
        ↓
Optional early stop if unchanged
        ↓
Run one extra pass
        ↓
Can still relax?
   ↙          ↘
 YES           NO
  ↓             ↓
Negative      No reachable
 cycle        negative cycle

Common Mistakes

Using Dijkstra with negative edges

Dijkstra’s greedy assumption breaks with negative weights.

Use Bellman-Ford when negative edges are possible.

Forgetting the unreachable check

Wrong:

if (dist[u] + w < dist[v])

Correct:

if (dist[u] != INF && dist[u] + w < dist[v])

Treating V-1 as “exactly V-1”

V - 1 is the maximum number of useful relaxation rounds.

With early termination:

if (!changed) break;

the algorithm can finish sooner.

Thinking any negative edge is a negative cycle

A negative edge is completely valid.

For example:

A → B (-5)

is not a cycle.

A reachable cycle whose total weight is negative is the problem.

Detecting unreachable negative cycles as source-reachable

The extra-pass check should include:

if (dist[u] == INF) continue;

Otherwise, a negative cycle in a disconnected component could incorrectly be reported as relevant to the source.

Recognition Cheat Sheet