☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Bellman Ford Algorithm

Hard TUF ID 2826 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed weighted graph with V vertices numbered 0 to V - 1, as a list of edges [u, v, w]. Weights may be negative. Given a source src, return an array where entry i is the shortest distance from src to i, using 10^8 for vertices that cannot be reached. If the graph contains a negative-weight cycle reachable from src, shortest distances are not defined (you could loop forever and keep lowering the cost), so return [-1] instead.

Constraints (GeeksforGeeks “Distance from the Source”): 1 ≤ V ≤ 500, 1 ≤ E ≤ V(V-1), -1000 ≤ w ≤ 1000.

Example 1

V = 3, edges = [[0,1,5], [1,0,3], [1,2,-1], [2,0,1]], src = 2
answer = [1, 6, 0]  // 2 -> 0 costs 1, then 0 -> 1 costs 5 more

Example 2

V = 3, edges = [[0,1,1], [1,2,-1], [2,0,-1]], src = 0
answer = [-1]       // 0 -> 1 -> 2 -> 0 has total weight -1, a negative cycle

Dijkstra cannot be used here. It finalises a vertex the moment it leaves the heap, assuming no later path can be shorter. A negative edge discovered later can break that assumption. Bellman-Ford makes no such assumption: it keeps improving distances until they cannot improve any further.

The idea behind Bellman-Ford

Relaxation. For an edge u → v with weight w, if dist[u] + w < dist[v], the path “best route to u, then this edge” beats the best known route to v, so we set dist[v] = dist[u] + w. Every shortest-path algorithm is a strategy for choosing which edges to relax and when. Bellman-Ford’s strategy is the bluntest one: relax every edge, and repeat.

Why V - 1 rounds are enough. If there is no negative cycle, some shortest path to each vertex is simple, so it has at most V - 1 edges: src = x0 → x1 → … → xm with m ≤ V - 1. Claim: after round r, dist[x_r] is correct. Round 0 holds because dist[src] = 0. If dist[x_(r-1)] is correct after round r - 1, then during round r the edge x_(r-1) → x_r gets relaxed and sets dist[x_r] to its true value. Relaxations never push a value below the true distance, because every value written is the length of an actual path. So after V - 1 rounds every distance is final, whatever order the edges are listed in.

Why round V detects a negative cycle. If all distances are final after V - 1 rounds, then one more round changes nothing. Conversely, suppose a negative cycle c0 → c1 → … → c0 is reachable and no edge on it can be relaxed: dist[c_(i+1)] ≤ dist[c_i] + w_i for every edge of the cycle. Adding these inequalities around the cycle, the dist terms cancel and we get 0 ≤ total cycle weight, contradicting that the cycle is negative. So some edge on it can always be relaxed, and round V will find it.

Approach 1: Classic Bellman-Ford

Intuition. Run the proof literally: V - 1 full rounds of relaxing every edge, then one extra round that only checks whether anything could still improve. Only relax from vertices that have been reached (dist[u] != INF). Otherwise INF + w with a negative w could look like a real distance, and a cycle that src cannot reach would be reported.

Algorithm.

  1. dist[src] = 0, all others 10^8.
  2. Repeat V - 1 times: for each edge [u, v, w], if dist[u] != INF and dist[u] + w < dist[v], set dist[v] = dist[u] + w.
  3. For each edge, if it can still be relaxed, return [-1].
  4. Return dist.
static int[] bellmanFord(int V, int[][] edges, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 1; round <= V - 1; round++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    for (int[] e : edges) {                          // round V: any improvement means a negative cycle
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != INF && dist[u] + w < dist[v]) return new int[]{-1};
    }
    return dist;
}

Complexity. Time O(V · E): V passes over all E edges. Space O(V) for the distance array. For V = 500 and E ≈ 250,000 that is about 1.25 × 10^8 cheap operations, which is acceptable but not fast.

Approach 2: Bellman-Ford with early exit

Intuition. The V - 1 bound is a worst case. Once a round changes nothing, no later round can change anything either, because each round reads only the current dist values and they are identical. So we track whether a round made any update and stop as soon as one is quiet. If the graph has a reachable negative cycle, every round makes an update (by the argument above), so if round V still changes something we report the cycle. This folds the detection round into the main loop.

Algorithm.

  1. dist[src] = 0, all others 10^8.
  2. For round = 1..V: relax every edge, remembering whether anything changed. If nothing changed, return dist.
  3. If the loop finishes, the V-th round still improved something, so return [-1].
static int[] bellmanFordEarlyExit(int V, int[][] edges, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 1; round <= V; round++) {
        boolean changed = false;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) return dist;                   // a quiet round: every distance is final
    }
    return new int[]{-1};                            // V rounds and still improving
}

Dry run on Example 1 (src = 2), edges in the given order:

round 0→1 (5) 1→0 (3) 1→2 (-1) 2→0 (1) dist after changed
1 skip (0 unreached) skip skip dist[0] = 1 [1, ∞, 0] yes
2 dist[1] = 6 9 > 1 5 > 0 1 = 1 [1, 6, 0] yes
3 6 = 6 no no no [1, 6, 0] no, return

Approach 1 would run rounds 1 and 2 (that is V - 1) and then a check round, which is the same work here. On a long chain listed in the right order the early exit finishes after two rounds instead of V.

Complexity. Worst case still O(V · E), for example a chain whose edges are listed backwards (the tests include one), where each round advances the frontier by exactly one edge. Best case O(E) when the first round already settles everything. Space O(V).

Edge cases and pitfalls