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.

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.

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.

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.