Bellman-Ford and Negative-Weight Edges

Bellman-Ford solves the single-source shortest path problem on weighted graphs, just like Dijkstra. The crucial difference is that Bellman-Ford handles negative edge weights and can detect negative cycles. The price you pay is O(V times E) time instead of O((V + E) log V).

When Negative Edges Matter

Negative edges show up in real problems more often than people expect. Currency arbitrage, where edges represent exchange rates, naturally produces negative log weights. Cost-benefit models, where some transitions reward the agent, also fit. Any model that allows a step to reduce total cost rather than only adding to it needs Bellman-Ford rather than Dijkstra.

A negative cycle is a cycle whose total edge weight is negative. If a negative cycle is reachable from the source, no shortest path is well defined, because you can loop the cycle arbitrarily many times to reduce cost without bound. Detecting this is one of Bellman-Ford’s superpowers.

The Relaxation Idea

The algorithm is built on a single operation: edge relaxation. For an edge u to v with weight w, if dist[u] + w improves dist[v], update dist[v]. Bellman-Ford applies this operation to every edge in the graph, then repeats the entire pass V minus one times.

Why V minus one passes? The shortest path between any two nodes in a graph without negative cycles uses at most V minus one edges. After k passes, every shortest path of length at most k edges is correctly computed. After V minus one passes, every shortest path is correct.

Python Implementation

We represent the graph as a list of edges, each a tuple of source, destination, and weight.

from math import inf

def bellman_ford(num_nodes, edges, source):
    dist = [inf] * num_nodes
    dist[source] = 0

    for _ in range(num_nodes - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("Negative cycle detected")
    return dist

edges = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -3),
    (2, 3, 4),
    (1, 3, 6),
]
print(bellman_ford(4, edges, 0))

The early exit when no edge is relaxed in a full pass is a common optimization. If a full pass changes nothing, no future pass will change anything either, so we can stop.

Detecting Negative Cycles

After the V minus one relaxation passes, we do one more pass. If any edge can still be relaxed, then there is a path that keeps getting shorter, which is only possible if a negative cycle is reachable from the source. The algorithm raises an error or returns a sentinel in that case.

To find which nodes are affected by negative cycles, mark every node whose distance can still be reduced as having distance negative infinity, then propagate that label to anything reachable from them.

Complexity Analysis

Bellman-Ford runs in O(V times E) time. We perform V minus one relaxation passes, and each pass touches all E edges. Space is O(V) for the distance array. There is no logarithmic factor because we do not use a priority queue.

On dense graphs where E is close to V squared, this becomes O(V cubed), which is the same order as Floyd-Warshall. If you need all-pairs shortest paths, Floyd-Warshall is often more convenient.

Bellman-Ford Versus Dijkstra

Dijkstra is faster but requires non-negative edge weights. Bellman-Ford is slower but handles negatives and detects negative cycles. If your weights are guaranteed non-negative, always pick Dijkstra. If you are unsure, or if negative weights are possible, use Bellman-Ford.

A practical middle ground is Johnson’s algorithm, which uses Bellman-Ford to reweight edges into non-negative values, then runs Dijkstra from each source. This gives all-pairs shortest paths in O(V times E log V) and beats Floyd-Warshall on sparse graphs.

SPFA: A Practical Speedup

The Shortest Path Faster Algorithm is a queue-based variant of Bellman-Ford. Instead of relaxing every edge each pass, it only relaxes edges out of nodes whose distance changed in the previous pass. On average graphs it runs much faster than vanilla Bellman-Ford, though its worst case is still O(V times E).

from collections import deque

def spfa(graph, source, num_nodes):
    dist = [inf] * num_nodes
    dist[source] = 0
    in_queue = [False] * num_nodes
    q = deque([source])
    in_queue[source] = True
    count = [0] * num_nodes

    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
                    count[v] += 1
                    if count[v] >= num_nodes:
                        raise ValueError("Negative cycle detected")
    return dist

The count array tracks how many times each node was queued. A node entering the queue V times or more signals a negative cycle.

Practical Notes

Bellman-Ford is the algorithm behind distance-vector routing protocols like RIP, where routers exchange distance estimates with neighbors. The classroom version of the algorithm maps almost directly onto the protocol’s message passing model.

For dense graphs with potential negatives and no need for cycle detection, Floyd-Warshall is often simpler. For sparse graphs or single-source queries, Bellman-Ford or SPFA wins.

If you want to compare costs to the non-negative case, revisit /blog/sorting-algorithms-overview for related complexity intuition and /blog/big-o-notation-explained for a refresher on the V times E term.

Wrap up

Bellman-Ford relaxes every edge V minus one times, computes shortest paths even with negative weights, and detects negative cycles via one extra pass. It is slower than Dijkstra but strictly more powerful. When negative edges are possible, this is the algorithm to reach for.