Bellman-Ford Algorithm

A Bit of History

The algorithm carries two names because it was discovered independently, from two different directions, within two years of each other. Richard Bellman — the same mathematician who invented dynamic programming itself in 1953 — described the recurrence in 1958 as a natural application of his own technique to shortest paths. Lester Ford Jr. had already outlined an equivalent method in a 1956 RAND Corporation report on network flow theory. The algorithm found an unglamorous but enormously important early home in computer networking: early distance-vector routing protocols (predecessors of today's RIP protocol) run essentially Bellman-Ford across the entire network, with each router treating itself as the source and broadcasting its known distances to its neighbors every cycle — a distributed, message-passing version of the exact same relaxation idea.

Working Principle

Bellman-Ford solves single-source shortest paths on a weighted graph that may contain negative edge weights (but for a well-defined answer to exist, no negative cycle reachable from the source). Its strategy is almost embarrassingly simple compared to Dijkstra's cleverness: relax every edge in the graph, and repeat this for \(V-1\) rounds.

def bellman_ford_pseudocode(vertices, edges, source):
    """
    edges: list of (u, v, weight) triples.
    Precondition: no negative cycle reachable from source (checked separately).
    """
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):     # V - 1 rounds
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w      # relax every edge, every round
    return dist

Why V-1 Rounds Are Enough

This is induction from Part 1, applied directly. Claim: after round \(k\), \(\text{dist}[v]\) is correct for every vertex \(v\) whose true shortest path uses at most \(k\) edges.

Base case (\(k=0\)): only the source itself has a 0-edge shortest path, and \(\text{dist}[\text{source}]=0\) is correct from initialization. Inductive step: assume the claim holds after round \(k\). Consider any vertex \(v\) whose true shortest path uses exactly \(k+1\) edges, with the last edge being \((u,v)\). Since a shortest path never repeats a vertex (Part 1), the sub-path to \(u\) uses at most \(k\) edges and is therefore correct in \(\text{dist}[u]\) by the inductive hypothesis. Round \(k+1\) relaxes every edge, including \((u,v)\) — so \(\text{dist}[v]\) becomes at most \(\text{dist}[u] + w(u,v)\), the true shortest distance. Since any simple path has at most \(V-1\) edges, \(V-1\) rounds suffice for every vertex.

Detecting Negative Cycles

Run one extra, \(V\)-th round of relaxation. If any distance still improves, a negative cycle reachable from the source must exist — because if no such cycle existed, every shortest path would have at most \(V-1\) edges and would already have stabilized. This single extra pass is how Bellman-Ford doubles as a negative-cycle detector, not just a shortest-path algorithm.

Complexity Analysis

\(V-1\) rounds, each relaxing all \(E\) edges:

$$\text{Time: } O(VE) \qquad \text{Space: } O(V)$$

A common practical optimization: stop early if an entire round produces no improvement at all — the distances have already converged and further rounds are provably wasted.

Implementation

def bellman_ford(vertices, edges, source):
    """
    edges: list of (u, v, weight).
    Returns (dist, has_negative_cycle).
    """
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0

    for i in range(len(vertices) - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break   # early exit: converged before V-1 rounds

    # One extra round: any further improvement means a negative cycle exists
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break

    return dist, has_negative_cycle

vertices = ["A", "B", "C", "D"]
edges = [("A", "B", 4), ("A", "C", 1), ("C", "B", 1), ("B", "D", 1), ("C", "D", 5)]

dist, has_neg_cycle = bellman_ford(vertices, edges, "A")
print(dist)               # {'A': 0, 'B': 2, 'C': 1, 'D': 3}
print(has_neg_cycle)      # False

#include <vector>
#include <unordered_map>
#include <tuple>
#include <limits>
#include <iostream>
using namespace std;

pair<unordered_map<string, long long>, bool>
bellmanFord(vector<string>& vertices, vector<tuple<string,string,int>>& edges,
            const string& source) {
    unordered_map<string, long long> dist;
    const long long INF = numeric_limits<long long>::max() / 2;
    for (auto& v : vertices) dist[v] = INF;
    dist[source] = 0;

    for (size_t i = 0; i + 1 < vertices.size(); i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }

    bool hasNegativeCycle = false;
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            hasNegativeCycle = true;
            break;
        }
    }
    return {dist, hasNegativeCycle};
}

int main() {
    vector<string> vertices = {"A", "B", "C", "D"};
    vector<tuple<string,string,int>> edges = {
        {"A", "B", 4}, {"A", "C", 1}, {"C", "B", 1}, {"B", "D", 1}, {"C", "D", 5}
    };
    auto [dist, hasNegCycle] = bellmanFord(vertices, edges, "A");
    cout << "Distance A->D: " << dist["D"] << endl;  // 3
    return 0;
}

import java.util.*;

class BellmanFord {
    record Edge(String u, String v, int weight) {}

    static Map<String, Long> run(List<String> vertices, List<Edge> edges,
                                   String source, boolean[] hasNegativeCycleOut) {
        Map<String, Long> dist = new HashMap<>();
        long INF = Long.MAX_VALUE / 2;
        for (String v : vertices) dist.put(v, INF);
        dist.put(source, 0L);

        for (int i = 0; i < vertices.size() - 1; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                if (dist.get(e.u()) != INF && dist.get(e.u()) + e.weight() < dist.get(e.v())) {
                    dist.put(e.v(), dist.get(e.u()) + e.weight());
                    updated = true;
                }
            }
            if (!updated) break;
        }

        boolean hasNegativeCycle = false;
        for (Edge e : edges) {
            if (dist.get(e.u()) != INF && dist.get(e.u()) + e.weight() < dist.get(e.v())) {
                hasNegativeCycle = true;
                break;
            }
        }
        hasNegativeCycleOut[0] = hasNegativeCycle;
        return dist;
    }

    public static void main(String[] args) {
        List<String> vertices = List.of("A", "B", "C", "D");
        List<Edge> edges = List.of(
            new Edge("A", "B", 4), new Edge("A", "C", 1), new Edge("C", "B", 1),
            new Edge("B", "D", 1), new Edge("C", "D", 5)
        );
        boolean[] hasNegCycle = new boolean[1];
        Map<String, Long> dist = run(vertices, edges, "A", hasNegCycle);
        System.out.println("Distance A->D: " + dist.get("D"));  // 3
    }
}

Real-World Applications

The other classic application is distance-vector routing (early RIP-style protocols): every router runs a local, distributed version of Bellman-Ford, exchanging distance vectors with neighbors until the whole network's routing tables converge.

Exercises

1. Run Bellman-Ford by hand on a graph with one negative edge (but no negative cycle) and verify it produces the same distances Dijkstra would fail to compute correctly.
2. Construct a 3-currency exchange-rate graph with a genuine arbitrage opportunity, transform it via \(-\log(\text{rate})\), and confirm Bellman-Ford's extra round detects the negative cycle.
3. Explain why the "early exit if no round produces an update" optimization is always safe — it can never cause the algorithm to stop before convergence.
4. Challenge: Modify the implementation to also reconstruct and print the actual negative cycle (not just detect its existence) once round \(V\) finds an improvement.

Limitations