Bellman-Ford Algorithm

Relax every edge, n-1 times

Bellman-Ford relaxes every edge (checks if going through it shortens the destination's distance) repeatedly, V-1 times. After V-1 rounds, all shortest paths (which use at most V-1 edges) are guaranteed found — even with negative weights.

Implementation

One extra pass after the main V-1 rounds checks if any distance can still shrink — if so, a negative cycle exists and shortest paths are undefined.

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError('negative cycle detected')
    return dist

Dijkstra vs Bellman-Ford

Bellman-Ford is O(V*E) — slower than Dijkstra's O((V+E) log V) — but handles negative weights and detects negative cycles, which Dijkstra cannot do at all.