Bellman-Ford Algorithm

Overview

The Bellman-Ford algorithm is a graph search algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted directed graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative cycles.

The algorithm works by relaxing all edges repeatedly. It performs V-1 iterations (where V is the number of vertices), and in each iteration, it relaxes all edges. If after V-1 iterations, we can still relax an edge, it means there's a negative cycle in the graph.

Bellman-Ford is particularly useful in network routing protocols, currency arbitrage detection, and any scenario where negative weights are present or need to be detected.

Bellman-Ford is the algorithm you reach for when Dijkstra's cannot help you, and the situations where it cannot help you turn out to be more common than the classical treatment suggests. Any shortest-path problem where the edge weights can be negative lives in Bellman-Ford's territory: currency exchange (an arbitrage opportunity is a negative cycle in the log-weighted exchange graph), network flow refinement, some reinforcement-learning value updates, and the internal iteration of algorithms like Johnson's all-pairs shortest paths. The algorithm's O(VE) complexity looks bad next to Dijkstra's O((V+E) log V), but negative weights force Bellman-Ford, and the difference is not "slower" but "possible at all."

History and the Ford–Fulkerson Line

The Bellman-Ford algorithm has a slightly unusual naming history. Richard Bellman published the recurrence that underlies the algorithm in 1958 as part of his book Dynamic Programming, the same book that introduced the phrase "dynamic programming" as the name for a general technique. Lester R. Ford Jr. had independently described what is essentially the same algorithm slightly earlier, in a 1956 RAND Corporation technical report on network flow. Edward F. Moore also published the same algorithm in 1957 in the context of routing telephone calls, and for this reason the algorithm is sometimes called Bellman–Ford–Moore in older literature. The modern convention settles on "Bellman-Ford," acknowledging Bellman's role in placing the algorithm within the broader dynamic-programming framework.

Ford's motivation was specifically the routing problem for the ARPANET's predecessor projects at RAND, and this is where Bellman-Ford's most consequential real-world deployment happened. The Routing Information Protocol (RIP), one of the earliest interior gateway protocols for IP networks (RFC 1058, published 1988), is a distributed implementation of Bellman-Ford. Each router in a RIP network maintains a distance vector to every other router and exchanges its vector with its immediate neighbours; each neighbour then applies the Bellman-Ford relaxation locally. The algorithm converges to the shortest paths across the whole network without any node ever needing a global view. RIP was the dominant interior routing protocol for the internet's first two decades and is still in use in some smaller networks, though OSPF (based on Dijkstra's algorithm with link-state broadcasting) has largely superseded it for large networks because it converges faster.

The "counting to infinity" problem in RIP, where a broken link can cause routers to increment their distance estimates unboundedly, is a real-world consequence of Bellman-Ford's distributed convergence properties, and RFC 2453 (RIP version 2) added mechanisms like split horizon and poisoned reverse specifically to work around it. If you have ever wondered why network protocols have such elaborate rules for how to advertise routes, some of that complexity traces directly back to the practical behaviour of Bellman-Ford under changing network topology.

Why Exactly V−1 Iterations?

The V−1 iteration count is not arbitrary and is worth understanding, because it is one of the key correctness proofs in shortest-path algorithms.

Claim: In a graph with no negative cycles, any shortest path uses at most V−1 edges. This is because a shortest path never revisits a vertex, if it did, the loop could be excised without increasing the total weight (assuming no negative cycles), giving a shorter path. A simple path in a graph of V vertices has at most V−1 edges.

Inductive argument: after k iterations of relaxing all edges, Bellman-Ford has computed correct shortest distances for every vertex reachable from the source by a path of at most k edges. This is provable by induction: at k = 0, only the source itself is reachable in zero edges, and its distance is correctly 0. At iteration k, for any vertex v whose shortest path uses at most k edges, the last edge on that path is some (u, v) where u's shortest path uses at most k−1 edges, and by inductive hypothesis, u's distance was already correct after iteration k−1. So when we relax edge (u, v) at iteration k, we correctly set dist[v] to its true minimum.

Combining the two: since any shortest path uses at most V−1 edges, after V−1 iterations Bellman-Ford has found all shortest distances. The Vth iteration is the negative-cycle check: if any edge can still be relaxed after V−1 iterations, then a path exists that uses V or more edges and is shorter than the best V−1-edge path, which means that path revisits at least one vertex, forming a cycle whose total weight is negative.

The early exit optimisation follows from the same argument. If a complete iteration relaxes nothing, then every shortest path has been found and further iterations will change nothing. On typical graphs, Bellman-Ford converges in far fewer than V−1 iterations, often O(diameter of the graph), and the early exit is well worth implementing.

Where Bellman-Ford Shines

Currency Arbitrage Detection

Suppose the foreign-exchange market lets you convert USD to EUR at rate r₁, EUR to JPY at r₂, and JPY to USD at r₃. An arbitrage opportunity exists if r₁ · r₂ · r₃ > 1, you end up with more USD than you started with.

Take the logarithm of both sides: log(r₁) + log(r₂) + log(r₃) > 0. Equivalently, −log(r₁) − log(r₂) − log(r₃) < 0. Build a graph where each currency is a vertex and each exchange rate r is an edge with weight −log(r). An arbitrage opportunity is now exactly a negative-weight cycle in this graph. Bellman-Ford's negative-cycle detection finds it in O(VE), which for the ~180 tradeable currencies in world markets is trivial. High-frequency trading firms run this algorithm continuously against live exchange rate feeds.

Distance-Vector Routing

RIP and its descendants (EIGRP, BGP's path-vector variant) all use Bellman-Ford's relaxation as their core update rule. The distributed nature of Bellman-Ford, each router only needs to know its immediate neighbours' distances, not the entire graph, is what made it the natural choice for early internet routing.

Constraint-Based Scheduling

Problems of the form "task A must start at least 3 minutes before task B" can be modelled as a graph with an edge from A to B of weight −3 (representing the constraint that time(B) − time(A) ≥ 3, or equivalently that going from A "costs" −3 units of time). Bellman-Ford on this constraint graph finds the tightest schedule satisfying all constraints, or reports infeasibility (a negative cycle). This is how many project scheduling algorithms and hardware timing analysis tools work internally.

Johnson's Algorithm

Floyd-Warshall solves all-pairs shortest paths in O(V³). For sparse graphs, Johnson's algorithm (Donald B. Johnson, 1977) is faster: O(V² log V + VE). It works by using Bellman-Ford once to reweight the edges so that they become non-negative while preserving shortest-path structure, then running Dijkstra from each vertex. Bellman-Ford's ability to handle negative weights is what makes the reweighting step possible.

How It Works

The algorithm follows these steps:

Initialize: Set distance to source as 0, and all other distances as infinity
Relax Edges: Repeat V-1 times:
- For each edge (u, v) with weight w
- If dist[u] + w < dist[v], update dist[v] = dist[u] + w
Check for Negative Cycles: After V-1 iterations, check if any edge can still be relaxed. If yes, negative cycle exists.
Result: Distances array contains shortest distances (or indicates negative cycle)

Bellman-Ford Algorithm Pseudocode


BellmanFord(graph, source):
    dist[source] = 0
    dist[v] = ∞ for all other vertices v
    parent[v] = null for all vertices
    
    // Relax edges V-1 times
    for i = 1 to V-1:
        for each edge (u, v) with weight w in graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
    
    // Check for negative cycles
    for each edge (u, v) with weight w in graph:
        if dist[u] + w < dist[v]:
            return "Negative cycle detected"
    
    return dist, parent

Implementation


def bellman_ford(edges, n, start):
    """
    edges: list of edges [(u, v, weight), ...]
    n:     number of vertices, passed in explicitly
    start: source vertex
    Returns: (distances, parent, has_negative_cycle)

    n MUST be a parameter. Deriving it with len(set(...)) over the edge list
    counts only vertices that appear in some edge, so any isolated vertex is
    dropped - which makes the array too short and the V-1 iteration count wrong.
    """
    dist = [float('inf')] * n
    dist[start] = 0
    parent = [-1] * n

    # Relax all edges V-1 times
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                changed = True
        if not changed:
            break          # early exit: a pass that relaxes nothing means we are done

    # An edge still relaxable after V-1 passes implies a negative cycle
    has_negative_cycle = any(
        dist[u] != float('inf') and dist[u] + w < dist[v]
        for u, v, w in edges
    )

    return dist, parent, has_negative_cycle

def reconstruct_path(parent, target):
    """Reconstruct shortest path from parent array"""
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = parent[current]
    return path[::-1] if path[0] == target else []

Complexity Analysis

Time Complexity: O(V × E) where V is vertices and E is edges
Space Complexity: O(V) - for distance and parent arrays

The algorithm is slower than Dijkstra's (O((V + E) log V)) but can handle negative weights and detect negative cycles, which Dijkstra cannot.

Negative Cycles

A negative cycle is a cycle in the graph where the sum of edge weights is negative. If such a cycle is reachable from the source, the shortest path is undefined (can be made arbitrarily short by going around the cycle).

Bellman-Ford detects negative cycles by checking if any edge can still be relaxed after V-1 iterations. Any shortest path visits at most V-1 edges, so after V-1 passes everything should have settled; if an edge still improves, no shortest path exists.

Two cautions when a negative cycle is reported. First, the returned dist array is meaningless in that case, do not use it. Second, only cycles reachable from the source are detected. To identify which vertices are affected, run V-1 further passes and mark every vertex still being relaxed, then propagate that mark to everything reachable from them, those are the vertices whose true distance is −∞.

Note also that the algorithm assumes a directed graph. A negative-weight edge in an undirected graph is a negative cycle, since you can traverse it back and forth indefinitely.

Example

Finding shortest paths from vertex 0:

Graph (5 vertices, one negative edge):

    0 --(4)--> 1 --(3)--> 3
    |                     ^
   (1)                    |
    |                    (-2)
    v                     |
    2 ---------------------+
    |
   (2)
    v
    4

Edges: 0->1 (4), 0->2 (1), 1->3 (3), 2->3 (-2), 2->4 (2)

V = 5, so we run V-1 = 4 relaxation passes, then a 5th checking pass.

Pass 1: relax every edge
  dist[0] = 0                       source
  dist[1] = 0 + 4    =  4           via 0->1
  dist[2] = 0 + 1    =  1           via 0->2
  dist[3] = 1 + (-2) = -1           via 2->3  (beats 4 + 3 = 7 via 1->3)
  dist[4] = 1 + 2    =  3           via 2->4

Pass 2: no edge improves -> early exit

Check pass: no edge can be relaxed -> no negative cycle

Result: dist = [0, 4, 1, -1, 3]

Note dist[4] = 3, reached as 0→2→4 at cost 1 + 2, vertex 4 hangs off vertex 2, not vertex 3.

When to Use Bellman-Ford

Bellman-Ford is ideal when:

Graph has negative edge weights
You need to detect negative cycles
Graph is sparse (few edges)
Currency arbitrage detection
Network routing with negative costs

Consider alternatives when:

All weights are non-negative → Use Dijkstra's (faster)
Unweighted graph → Use BFS (simpler)
All-pairs shortest paths → Use Floyd-Warshall

Bellman-Ford vs Other Algorithms

Algorithm	Negative Weights	Time Complexity	Best For
Dijkstra's	No	O((V + E) log V)	Non-negative weights
Bellman-Ford	Yes	O(V × E)	Negative weights, cycle detection
Floyd-Warshall	Yes	O(V³)	All-pairs shortest paths

Real-World Applications

Currency Arbitrage: Detecting profitable currency exchange cycles
Network Routing: Routing with negative costs (e.g., refunds)
Game Theory: Finding optimal strategies with negative payoffs
Resource Allocation: Optimizing with negative costs

Related Algorithms

Explore other searching algorithms:

Dijkstra's Algorithm - For non-negative weights
Floyd-Warshall Algorithm - All-pairs shortest paths
A* Algorithm - Heuristic-based search
Back to Graph Algorithms Overview