DSA Graphs

Bellman-Ford Algorithm

Why does Dijkstra settle the wrong city when one toll is a rebate? The courier graph has a negative edge. At FX desks, a USD→EUR→GBP→USD loop can print money: that is a .

Bellman-Ford repeats over all edges. After V−1 passes, finite distances are final unless a still improves something on the extra pass.

Algorithm journey

dist[s]=0, others ∞

Skip relaxing from infinity forever.

Propagate cheapest ≤k-edge paths.

Extra pass

Any reachable improvement ⇒ negative cycle.

Mark −∞ region

BFS/DFS outward from improved vertices.

What actually happens

Naive idea: run Dijkstra anyway. Breaks when a cheaper path uses a negative edge after a vertex was already settled. Or: report “negative cycle” from any improving edge on pass V, even if its tail is unreachable from the source. Wrong for this query.

Better idea: do not finalize early. Propagate improvements edge by edge. The says after pass k you know all optima that use at most k edges. A simple finite path needs ≤ V−1 edges.

The improved design still fails if you relax from ∞, mark only one cycle vertex (downstream stays falsely finite), or reconstruct parents after a cycle (the chain can loop forever).

Invariant

After pass k, dist[v] is no greater than the cheapest source-to-v walk using at most k edges (when dist[v] is finite). If a finite optimum exists, V−1 passes suffice. A still-improvable reachable edge on pass V proves a reachable negative cycle.

How to choose Bellman-Ford

1. Any negative weights? Yes: Bellman-Ford (or DAG topo if acyclic). No: Dijkstra is usually faster.

2. Need cycle detection / arbitrage? The extra pass is the feature, not a bug.

3. Sparse or dense? Cost is Θ(V·E). At V=10⁴, E=10⁵ that is ~10⁹ edge looks: often too slow; constrain the model or switch algorithms.

Quantitative check

V−1 passes × E edges ≈ V·E relaxations. For V=500, E=2000 that is about 10⁶ ops: fine. For V=10⁴, E=5·10⁴ it approaches 5·10⁸: budget carefully. Dijkstra on non-negative edges would be closer to (V+E) log V.

Interactive Bellman-Ford demo

Click "Bellman-Ford" to see it relax edges repeatedly. It tries to improve the path to every node, V-1 times.

Start:

Ready to find shortest path!

A∞

B∞

C∞

D∞

E∞

Priority Queue

Queue is empty

Sorted by distance (Min-Heap)

Pass-by-pass invariant lab

Compare finite shortest paths with a source-reachable negative cycle. The extra pass is meaningful only for edges whose tail is already reachable.

Bellman–Ford pass invariant lab

Compare a finite graph with a reachable negative cycle. Snapshots use a previous-pass copy so the “at most k edges” proof is visible.

Snapshot 1 / 6

Initialize

The source is zero; every other vertex is unreachable until an edge supplies a finite witness.

Pass position

improved

∞

Directed edge list scanned each pass
Edge	Weight	Current candidate
S → A	4	0 + 4 = 4
S → B	5	0 + 5 = 5
A → C	-2	skip: tail is ∞
B → C	1	skip: tail is ∞
C → T	3	skip: tail is ∞

Invariant checkpoint

Infinity is a semantic state, not a large path. Never evaluate INF + weight.

Three outcomes, not two

Finite distance

The vertex is reachable and no reachable negative cycle can flow into it. Return its distance and parent path.

Unreachable (+∞)

No source path exists. Its parent remains absent; a negative cycle elsewhere in the graph is irrelevant.

Unbounded below (−∞)

A reachable negative cycle can reach this vertex. No finite shortest path exists because repeating the cycle keeps lowering cost.

An extra-pass relaxation proves that some reachable negative cycle influences the relaxed vertex. To mark every undefined answer, seed all vertices improved on that pass and traverse outward through the graph.

📝 Algorithm Steps

Initialize

Set distance to start node as 0, and infinity for all others.

Relax Edges (V-1 Times)

Iterate through ALL edges V-1 times. For each edge (u, v), if dist[u] + weight < dist[v], update dist[v].

Detect Negative Cycles

Iterate one more time. If any edge can still be relaxed, a negative weight cycle exists!

🔄 Why V-1 Iterations?

In a simple path (no cycles), the longest possible path has V-1 edges. Each iteration propagates the shortest path by at least one edge. So, V-1 iterations guarantee the shortest path reaches the furthest node.

💼 Real World Application

RIP (Routing Information Protocol): An older internet routing protocol uses Bellman-Ford to find the best path for data packets, using hop count as the metric.

Correctness invariant and proof sketch

After pass k, dist[v] is no greater than the cheapest source-to-v path using at most k edges.

Base case k=0: the empty path gives the source distance 0; no other zero-edge path exists.
Inductive step: any path of at most k edges ends with an edge u→v after a prefix of at most k−1 edges. The prior pass represents that prefix; relaxing u→v represents the whole path.
Why V−1: if a finite optimum exists, remove non-negative repeated cycles from an optimal walk. What remains is a simple path with at most V−1 edges.
Detection: if a reachable edge still improves afterward, its improving witness contains a repeated vertex whose cycle has negative total weight.

In-place edge scans may propagate across several edges in one pass and converge earlier. That optimization does not weaken the at-most-k guarantee; early exit is valid when an entire pass changes nothing.

Worked trace: negative edge, finite answer

Edges are S→A (4), S→B (5), A→C (−2), B→C (1), C→T (3). The negative edge is safe because no negative cycle is reachable.

Synchronous pass	A	B	C	T	New reach
0	∞	∞	∞	∞	source only
1	4	5	∞	∞	A, B
2	4	5	2	∞	C via A
3	4	5	2	5	T via C
4 + check	4	5	2	5	stable; no cycle

⚡ Complexity Analysis

Time Complexity

•
O(V × E)
We relax E edges, V-1 times.

Space Complexity

•
O(V)
To store distances for each vertex.

💻 Implementation

The implementation is straightforward: a nested loop to relax edges.

Python

python

def bellman_ford(graph, num_vertices, start):
    """
    Bellman-Ford Algorithm to find shortest paths
    
    Args:
        graph: List of edges [(u, v, weight), ...]
        num_vertices: Total number of vertices
        start: Starting vertex
    
    Returns:
        List of shortest distances, or None if negative cycle detected
    """
    # 1. Initialize distances
    distances = [float('infinity')] * num_vertices
    distances[start] = 0

    # 2. Relax all edges V-1 times
    for _ in range(num_vertices - 1):
        for u, v, weight in graph:
            if distances[u] != float('infinity') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # 3. Check for Negative Cycles
    for u, v, weight in graph:
        if distances[u] != float('infinity') and distances[u] + weight < distances[v]:
            print("Graph contains negative weight cycle")
            return None

    return distances

# Example Usage
# Edges: (u, v, weight)
edges = [
    (0, 1, -1),
    (0, 2, 4),
    (1, 2, 3),
    (1, 3, 2),
    (1, 4, 2),
    (3, 2, 5),
    (3, 1, 1),
    (4, 3, -3)
]
num_vertices = 5

distances = bellman_ford(edges, num_vertices, 0)
if distances:
    print(f"Shortest distances from node 0: {distances}")
    # Output: Shortest distances from node 0: [0, -1, 2, -2, 1]

Java

java

import java.util.*;

class Edge {
    int src, dest;
    long weight;
    Edge(int src, int dest, long weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

public class BellmanFord {
    public static void bellmanFord(List<Edge> edges, int V, int start) {
        final long INF = Long.MAX_VALUE;
        long[] dist = new long[V];
        Arrays.fill(dist, INF);
        dist[start] = 0L;

        // 1. Relax all edges V-1 times
        for (int i = 1; i < V; ++i) {
            boolean changed = false;
            for (Edge edge : edges) {
                int u = edge.src;
                int v = edge.dest;
                long weight = edge.weight;
                
                if (dist[u] == INF) continue; // unreachable tails do not relax
                long candidate = Math.addExact(dist[u], weight);
                if (candidate < dist[v]) {
                    dist[v] = candidate;
                    changed = true;
                }
            }
            if (!changed) break;
        }

        // 2. Check for a negative cycle reachable from start
        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            long weight = edge.weight;
            
            if (dist[u] != INF && Math.addExact(dist[u], weight) < dist[v]) {
                System.out.println("A source-reachable negative cycle exists");
                return;
            }
        }

        // Print distances
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; ++i)
            System.out.println(i + "\t\t" + (dist[i] == INF ? "INF" : dist[i]));
    }

    public static void main(String[] args) {
        int V = 5; // Number of vertices
        List<Edge> edges = new ArrayList<>();
        
        edges.add(new Edge(0, 1, -1));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 2));
        edges.add(new Edge(1, 4, 2));
        edges.add(new Edge(3, 2, 5));
        edges.add(new Edge(3, 1, 1));
        edges.add(new Edge(4, 3, -3));

        bellmanFord(edges, V, 0);
        
        // Output:
        // Vertex Distance from Source
        // 0		0
        // 1		-1
        // 2		2
        // 3		-2
        // 4		1
    }
}

Production-safe Java: classify every vertex

Detecting a cycle is often not enough. This template distinguishes unreachable vertices, finite answers, and every vertex downstream of a source-reachable negative cycle; path reconstruction rejects the latter two unsafe states.

java

import java.util.*;

final class BellmanFordAnalysis {
    static final long INF = Long.MAX_VALUE;

    static final class Edge {
        final int from, to;
        final long weight;
        Edge(int from, int to, long weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static final class Result {
        final int source;
        final long[] distance;
        final int[] parent;
        final boolean[] unboundedBelow;
        Result(int source, long[] distance, int[] parent,
               boolean[] unboundedBelow) {
            this.source = source;
            this.distance = distance;
            this.parent = parent;
            this.unboundedBelow = unboundedBelow;
        }
    }

    static Result solve(int n, List<Edge> edges, int source) {
        if (source < 0 || source >= n) throw new IllegalArgumentException("bad source");
        List<List<Integer>> outgoing = new ArrayList<>();
        for (int i = 0; i < n; i++) outgoing.add(new ArrayList<>());
        for (Edge edge : edges) {
            if (edge.from < 0 || edge.from >= n || edge.to < 0 || edge.to >= n) {
                throw new IllegalArgumentException("bad endpoint");
            }
            outgoing.get(edge.from).add(edge.to);
        }

        long[] dist = new long[n];
        int[] parent = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);
        dist[source] = 0L;

        for (int pass = 1; pass < n; pass++) {
            boolean changed = false;
            for (Edge edge : edges) {
                if (dist[edge.from] == INF) continue;
                long candidate = Math.addExact(dist[edge.from], edge.weight);
                if (candidate >= dist[edge.to]) continue;
                dist[edge.to] = candidate;
                parent[edge.to] = edge.from;
                changed = true;
            }
            if (!changed) break;
        }

        // A Vth-round improvement is relevant only when its tail is reachable.
        boolean[] unbounded = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (Edge edge : edges) {
            if (dist[edge.from] == INF) continue;
            long candidate = Math.addExact(dist[edge.from], edge.weight);
            if (candidate < dist[edge.to] && !unbounded[edge.to]) {
                unbounded[edge.to] = true;
                queue.add(edge.to);
            }
        }

        // Every vertex reachable from such an improvement is also −infinity.
        while (!queue.isEmpty()) {
            int u = queue.removeFirst();
            for (int v : outgoing.get(u)) {
                if (unbounded[v]) continue;
                unbounded[v] = true;
                queue.addLast(v);
            }
        }
        return new Result(source, dist, parent, unbounded);
    }

    static List<Integer> finitePathTo(Result result, int target) {
        if (target < 0 || target >= result.distance.length) {
            throw new IllegalArgumentException("bad target");
        }
        if (result.distance[target] == INF) return List.of();
        if (result.unboundedBelow[target]) {
            throw new IllegalStateException("no finite shortest path");
        }

        List<Integer> reversed = new ArrayList<>();
        boolean[] seen = new boolean[result.distance.length];
        for (int at = target; at != -1; at = result.parent[at]) {
            if (seen[at]) throw new IllegalStateException("parent cycle");
            seen[at] = true;
            reversed.add(at);
            if (at == result.source) {
                Collections.reverse(reversed);
                return reversed;
            }
        }
        throw new IllegalStateException("parent chain missed source");
    }
}

Common bugs

Bug	Consequence	Correct guardrail
Relaxing from infinity	The sentinel can overflow and create fake reachability.	Skip when `dist[u] == INF`.
Reporting any graph cycle	An unreachable negative cycle does not affect this source.	The Vth-round edge tail must be reachable.
Marking one cycle vertex only	Downstream vertices are also unbounded below.	Traverse outward from every Vth-round improvement.
Using `int` for path cost	Repeated negative or positive additions can wrap.	Use `long` and checked/bounded addition.
Returning parents after a cycle	The chain can loop forever and no optimum exists.	Reject affected targets and keep a reconstruction cycle guard.
Assuming edge-list order	A lucky order propagates farther per pass and hides missing passes.	Correctness must hold for every edge ordering.

SPFA, early exit, and limitations

Early termination

If an entire pass over all edges relaxes nothing, all shortest paths are finalized; stop early instead of always doing V−1 rounds. The extra “cycle check” pass still runs once from that stable state.

Queue-based SPFA (heuristic)

Shortest Path Faster Algorithm relaxes only vertices whose distance changed, using a queue. Average case can approach Dijkstra-like behavior on many inputs, but adversarial graphs force it back to worst-case O(V·E): do not rely on SPFA for hard guarantees in contests.

DAG shortcut

If the graph is a DAG, one topological-order relaxation pass gives shortest paths even with negative edges (there are no cycles): O(V+E), strictly better than generic Bellman–Ford.

Short takeaway

Bellman-Ford finds single-source distances with negative edges by relaxing all edges V−1 times, then uses one extra reachable pass to detect negative cycles. Prefer Dijkstra when all weights are non-negative; prefer a DAG topo pass when there are no cycles at all.

Exercises

Draw a graph with a negative cycle unreachable from s. After V−1 passes and the extra check, which distances stay finite, and which edges must not trigger a “cycle” report for this source?
Trace the worked example S→A(4), S→B(5), A→C(−2), B→C(1), C→T(3). After which pass does C first become 2, and why is Dijkstra unsafe if you pretend the −2 edge is “almost non-negative”?
V=8000, E=40000, mixed signs, no DAG promise. Estimate V·E. Would you ship Bellman-Ford, constrain weights, or remodel the problem?

Primary sources

Bellman, R. (1958): On a routing problem.
Ford, L. R., Jr.: Network flow / path algorithms (same era as max-flow work).
Cormen et al., CLRS: The Bellman-Ford algorithm and negative-cycle detection.