Bellman-Ford algorithm explained: how it works, code and complexity

What problem Bellman-Ford solves

Dijkstra's algorithm is fast but requires non-negative edge weights. Some problems naturally have negative weights: a refund, a gain in a currency exchange, or an energy cost that can go below zero. Bellman-Ford handles these graphs correctly and also tells you when no shortest path exists because of a negative cycle, a loop you could go around forever to make the cost smaller and smaller.

The algorithm is named after Richard Bellman and Lester Ford Jr., who published versions of it in the 1950s.

The idea in plain words

1. Set the distance of the start node to 0 and all others to infinity.
2. Repeat V − 1 times: for every edge u → v with weight w, if dist[u] + w < dist[v], update dist[v].
3. Do one more pass over all edges. If any distance still improves, report a negative cycle.

Why V − 1 rounds? A shortest path without cycles uses at most V − 1 edges. After round k, every node whose shortest path has at most k edges already has its correct distance, so V − 1 rounds cover every simple path.

Worked example, step by step

Directed graph with 4 nodes and the edges S→A (4), S→B (5), B→A (−3), A→C (3). The edges are processed in this order in every round.

In round 1, A first becomes 4 through S→A, then improves to 2 through B→A, and C uses the improved value. Dijkstra's algorithm would finalize A at 4 before looking at B, which is exactly the mistake a negative edge causes.

Python implementation

Bellman-Ford works on a plain list of edges, which makes it short to write:

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

Adding an edge C → B with weight −6 creates the cycle B → A → C → B with total weight −3 + 3 − 6 = −6, so the extra pass finds it:

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

The dist[u] != INF check skips edges that leave nodes not reached yet. In Python, float("inf") + w is still infinity, so the check mainly saves work. In languages that use a large integer as infinity, it prevents overflow and false updates.

Time and space complexity

On a graph with 1,000 nodes and 10,000 edges that is up to about 10 million relaxations, so Dijkstra is much faster when all weights are non-negative.

Variants and common mistakes

• Early exit: stop when a full round changes nothing. This is safe and often makes the algorithm much faster in practice.
• SPFA (shortest path faster algorithm): only re-relax edges out of nodes whose distance changed, using a queue. It is often fast but has the same O(V × E) worst case.
• Hop-limited paths: running exactly k rounds, using a copy of the distances from the previous round, gives the cheapest path with at most k edges. This solves "cheapest flights within k stops".
• Finding the cycle itself: keep a parent map; when the extra pass updates node v, follow parents V times to land inside the cycle, then walk until you return to the same node.

When to use it and real-world uses

• Use Bellman-Ford when edge weights can be negative or when you must detect negative cycles. Otherwise prefer Dijkstra.
• Distance-vector routing protocols, such as RIP, use the distributed Bellman-Ford idea: each router repeatedly updates its distance estimates from its neighbors' estimates.
• Currency arbitrage: with weights equal to -log(rate), a negative cycle is a sequence of exchanges that ends with more money than it started with.
• Johnson's algorithm runs Bellman-Ford once to re-weight a graph so that Dijkstra can then be used from every node for all-pairs shortest paths.
• Difference constraints (systems of inequalities like x - y <= c) can be solved as shortest paths; a negative cycle means no solution exists.