Bellman-Ford

Bellman-Ford finds shortest paths from one start vertex even when some edge weights are negative.

It can also detect negative cycles reachable from the start.

Core Idea

The algorithm repeatedly relaxes every edge. After enough passes, every shortest path without a cycle has had enough chances to propagate its distance.

For V vertices, shortest simple paths use at most V - 1 edges, so the main relaxation loop runs V - 1 times.

Function Contracts

bellman_ford(vertices, edges, start) expects a collection of vertices, an edge list of (source, target, weight) triples, and a start vertex.

It returns shortest-distance estimates from start when no reachable negative cycle affects the result. has_negative_cycle(edges, distance) checks whether one more relaxation is still possible after the main passes.

Python Example

def bellman_ford(vertices, edges, start):
    distance = {vertex: float("inf") for vertex in vertices}
    distance[start] = 0
 
    for _ in range(len(vertices) - 1):
        changed = False
        for source, target, weight in edges:
            if distance[source] + weight < distance[target]:
                distance[target] = distance[source] + weight
                changed = True
        if not changed:
            break
 
    return distance

edges is a list of (source, target, weight) triples.

Negative Cycle Check

After V - 1 passes, one more successful relaxation means a negative cycle is reachable:

def has_negative_cycle(edges, distance):
    for source, target, weight in edges:
        if distance[source] + weight < distance[target]:
            return True
    return False

If a negative cycle can be used, the shortest path may be undefined because going around the cycle repeatedly keeps reducing the cost.

Why It Works

After one pass, all shortest paths that use at most one edge have been considered. After two passes, paths with at most two edges have been considered. After V - 1 passes, every simple shortest path has been considered because a simple path cannot contain more than V - 1 edges.

Complexity

Bellman-Ford runs O(VE) time because it may scan every edge for V - 1 rounds. It uses O(V) space for distances.

Failure Example

If a reachable cycle has total negative weight, repeatedly going around the cycle keeps making the path cheaper. In that case, there is no finite shortest path value for affected vertices.

Bellman-Ford can detect this by checking whether any edge can still be relaxed after V - 1 passes.

Common Confusions

Negative edges are not the same as negative cycles. A negative edge can be fine. A reachable negative cycle means there may be no well-defined shortest path.

Bellman-Ford is usually slower than Dijkstra on non-negative weighted graphs.

Another common mistake is forgetting reachability. A negative cycle that cannot be reached from the start may not affect shortest paths from that start.

When To Use It

Use Bellman-Ford when negative edge weights may exist, when negative cycle detection matters, or when the edge-list relaxation model is easier to express.

Do not use it by default for large non-negative graphs where Dijkstra is appropriate.

The Main Point

Bellman-Ford trades speed for tolerance of negative edges and reachable negative-cycle detection.