Bellman-Ford Algorithm

Bellman-Ford computes shortest paths even with negative edge weights and detects negative cycles, at a cost of O(V*E).

Relax every edge, repeatedly

Bellman-Ford finds shortest paths from a source in a weighted graph that may contain negative edge weights. It relaxes every edge V-1 times, where V is the number of vertices. Each full pass lets shortest-path information propagate one more edge along, so after V-1 passes every shortest path, which has at most V-1 edges, is found.

Detecting negative cycles

A shortest path is only well defined if no reachable cycle has negative total weight, since you could loop it forever to drive the cost down without bound. After the V-1 passes, one more relaxation pass is run: if any edge can still be relaxed, a negative cycle is reachable, and Bellman-Ford reports it. This detection is a capability Dijkstra's algorithm lacks.

• Time: O(V*E)
• Handles negative edge weights
• Detects reachable negative cycles
• Slower than Dijkstra but more general

def bellman_ford(vertices, edges, src):
    dist = {v: float('inf') for v in vertices}
    dist[src] = 0
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError('negative cycle')
    return dist

An early-exit optimisation

If a full pass over all edges relaxes nothing, every distance is already final and the algorithm can stop early. On many graphs this terminates well before the V-1 passes are exhausted. The queue-based SPFA variant applies the same idea by only reprocessing vertices whose distance changed, though it retains the same O(V*E) worst case.

When to choose it

Use Bellman-Ford when edge weights can be negative, as in currency-arbitrage detection or problems where costs and rebates mix. It is slower than Dijkstra's O((V+E) log V), so on graphs with only non-negative weights Dijkstra is preferred. For all-pairs shortest paths with negative edges, Floyd-Warshall or Johnson's algorithm, which uses Bellman-Ford once to reweight edges, applies.