Bellman–Ford

Why it costs this much

Each of the V − 1 rounds relaxes all E edges.

Code

def bellman_ford(n, edges, src):           # edges = [(u, v, w), ...]
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):                 # V - 1 rounds
        for u, v, w in edges:              # E edges per round: O(V * E) total
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Common pitfalls

It is slow on large graphs. A negative cycle makes shortest paths undefined, so run one extra round: if any distance still drops, a negative cycle exists.

Operation by operation

Bellman-Ford shortest path. Relaxes every edge up to V−1 times. Handles negative weights and detects negative cycles.