☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Bellman ford algorithm

Hard TUF ID 518 SDE

Java source ↗ Edit this article ↗

Problem

You are given a directed weighted graph with V vertices numbered 0 to V - 1, a list of edges {u, v, w} (an edge from u to v of weight w), and a source src. Weights may be negative. Return the shortest distance from src to every vertex. Following the sheet’s version (GFG, “Distance from the Source (Bellman-Ford Algorithm)”):

Constraints in the usual version: V up to a few hundred, E up to V(V - 1), |w| ≤ 1000.

Example 1

V = 3, src = 2, edges = [0→1 (5), 1→0 (3), 1→2 (-1), 2→0 (1)]
answer = [1, 6, 0]       // 2→0 costs 1, 2→0→1 costs 1 + 5 = 6

Example 2

V = 3, src = 0, edges = [0→1 (1), 1→2 (-1), 2→0 (-1)]
answer = [-1]            // the cycle 0→1→2→0 weighs -1, so distances can drop forever

Example 3 (why Dijkstra is not enough)

V = 3, src = 0, edges = [0→1 (2), 0→2 (5), 2→1 (-4)]
answer = [0, 1, 5]       // 0→2→1 costs 5 - 4 = 1; Dijkstra would settle vertex 1 at 2 too early

Approach 1: Classic Bellman-Ford

Intuition. Relaxing an edge u → v means: if dist[u] + w < dist[v], lower dist[v] to dist[u] + w. Relaxation is always safe, because every finite dist value is the cost of a real walk from src, and it never increases anything. The question is how many relaxations are enough.

Claim: after k rounds that each relax every edge, dist[v] is at most the cost of the cheapest path from src to v that uses at most k edges. Induction: such a path ends with some edge u → v, and its prefix is a path to u with at most k - 1 edges. After k - 1 rounds, dist[u] is no worse than that prefix, so relaxing u → v in round k brings dist[v] down to at most the full path cost.

If there is no reachable negative cycle, some shortest path to each vertex is simple and has at most V - 1 edges, so V - 1 rounds finish the job. If after those rounds some edge can still be relaxed, then a walk of V or more edges beats every simple path, and that is only possible when a negative cycle is reachable.

Algorithm.

  1. dist[src] = 0, everything else INF = 10^8.
  2. Repeat V - 1 times: for every edge with dist[u] != INF, relax it.
  3. One more pass: if any edge with dist[u] != INF still relaxes, return {-1}. Otherwise return dist.
static final int INF = 100_000_000;                        // "unreachable" marker used by the original problem

/** Approach 1: textbook Bellman-Ford. V - 1 rounds that relax every edge, then one extra round to detect a negative cycle. O(V * E) time, O(V) space. */
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) {
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return new int[]{-1};   // still improvable: negative cycle
    }
    return dist;
}

Complexity. Time O(V · E): V passes over all edges. Space O(V) for the distance array.

The dist[u] != INF guard matters for two reasons. Without it, an unreachable vertex sitting at 10^8 plus a negative edge would push a neighbour just below 10^8 and make it look reachable. It is also what restricts the negative-cycle check to cycles reachable from src; a negative cycle in a part of the graph the source never touches does not affect any answer.

Approach 2: Better, stop when a round changes nothing

Intuition. Each round is a deterministic function of the current dist array. If a full round changes nothing, the next round sees the same array and also changes nothing, so the distances are final and we can stop. On many inputs this happens after only a few rounds; if the edges happen to be listed in path order, a single round settles everything. We can fold the negative-cycle check into the same loop: allow up to V rounds, and if the V-th round still changes something, a negative cycle is reachable.

Algorithm.

  1. Initialise as before.
  2. For round = 1 .. V: relax every edge and remember whether anything changed.
    • If nothing changed, return dist.
    • If something changed in round V, return {-1}.
static int[] earlyExit(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;                         // stable: every distance is final
        if (round == V) return new int[]{-1};              // a V-th round still improved something
    }
    return dist;
}

Complexity. Worst case still O(V · E) time, but the best case drops to O(E) (one round confirms nothing changes after the first). Space O(V).

Approach 3: Queue-based Bellman-Ford (SPFA)

Intuition. In any round, the only edges that can produce an improvement are those leaving a vertex whose distance dropped since its edges were last relaxed. Every other relaxation repeats a comparison that already failed. So keep a FIFO queue of vertices whose distance just improved, and only relax their outgoing edges. A vertex already waiting in the queue is not added twice.

Negative-cycle detection needs a different test, because there are no numbered rounds. Track len[v], the number of edges on the walk that produced the current dist[v]. A real shortest path needs at most V - 1 edges. If len[v] reaches V, the walk repeats a vertex. That repeated loop was taken only because it strictly lowered the distance at the vertex where it closes, so the loop has negative weight.

Algorithm.

  1. Build an adjacency list. dist[src] = 0, len[src] = 0, enqueue src.
  2. Pop u. For each edge u → v that relaxes: update dist[v], set len[v] = len[u] + 1; if len[v] ≥ V, return {-1}; enqueue v if it is not already queued.
  3. When the queue empties, return dist.
static int[] spfa(int V, int[][] edges, int src) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
    int[] dist = new int[V], len = new int[V];             // len[v]: number of edges on the walk that gave dist[v]
    Arrays.fill(dist, INF);
    dist[src] = 0;
    boolean[] inQueue = new boolean[V];
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(src);
    inQueue[src] = true;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        inQueue[u] = false;
        for (int[] e : adj.get(u)) {
            int v = e[0];
            if (dist[u] + e[1] < dist[v]) {
                dist[v] = dist[u] + e[1];
                len[v] = len[u] + 1;
                if (len[v] >= V) return new int[]{-1};     // a shortest simple path has at most V - 1 edges
                if (!inQueue[v]) {
                    queue.add(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    return dist;
}

Dry run on Example 1 (src = 2):

Pop Edges relaxed Change Queue after
2 2→0 (1) dist[0] = 1, len[0] = 1 [0]
0 0→1 (5) dist[1] = 6, len[1] = 2 [1]
1 1→0 (3), 1→2 (-1) none: 9 > 1 and 5 > 0 []

The answer [1, 6, 0] comes out after four edge checks. Approach 1 makes twelve on the same input: two rounds plus the detection pass, each over all four edges.

Complexity. Worst case O(V · E) time, the same as classic Bellman-Ford (there are graphs built specifically to make SPFA slow), but on typical inputs it does far fewer relaxations. Space O(V + E) for the adjacency list and queue.

Edge cases and pitfalls