Bellman-Ford & Floyd-Warshall

Dijkstra is the go-to algorithm for shortest paths — until an edge has a negative weight, where it quietly gives wrong answers. Bellman-Ford is the slower but sturdier alternative: it handles negative edges, and as a bonus it can tell you when the graph has a negative cycle (a loop you could ride forever to make the cost go to minus infinity).

Intuition

Imagine dist[v] is the cheapest price you currently know to reach city v from the source. Every edge is a special offer: "fly from u to v for w dollars." Relaxing an edge is just checking whether that offer plus the known price of reaching u beats your current best price for v.

Why repeat the whole sweep V-1 times? A shortest path can pass through at most V-1 edges (any more and it would revisit a node — a pointless loop). Each full pass guarantees that paths using one more edge than before get accounted for. After V-1 passes, even the longest possible shortest path has been fully discovered.

Walk through it

The canvas on the right shows a 4-node directed graph. Node 0 is the source, so it starts at d[0]=0; everyone else starts at infinity. Watch the edge 1 -> 2 — its weight is -3, the negative edge that makes this interesting.

Step through a pass and the highlighted edge is the one being relaxed; when an offer wins, the destination node's d[...] label drops to a smaller number. The key moment: after 0 -> 1 sets d[1]=4, relaxing 1 -> 2 gives 4 + (-3) = 1, which beats the direct 0 -> 2 = 5. So the cheapest way to reach node 2 is the detour 0 -> 1 -> 2. A second pass changes nothing — the distances have converged — and a final check pass finds no further improvement, proving there is no negative cycle.

The code, line by line

def bellman_ford(n, edges, src):
    dist = [float("inf")] * n
    dist[src] = 0
 
    for _ in range(n - 1):            # V-1 passes
        for u, v, w in edges:         # relax every edge
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    for u, v, w in edges:             # one more pass
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            raise ValueError("negative cycle")
    return dist

• Lines 2-3 set up: everything is unreachable (infinity) except the source at distance 0.
• Line 5 is the outer V-1 loop — the number of passes. It does not depend on the data; it always runs V-1 times.
• Line 6 loops over every edge. The order of edges does not affect correctness, only how fast distances settle.
• Line 7 is the relaxation test. The dist[u] != inf guard stops us from doing inf + w arithmetic on a node we have not reached yet.
• Line 8 is the actual update — the only line that lowers a distance.
• Lines 10-12 are the negative-cycle detector: after V-1 passes everything should be final, so if any edge can still relax, a negative cycle exists and the "shortest path" is undefined.

Complexity

Bellman-Ford is O(V·E) because it makes V-1 passes and each pass touches all E edges. That is slower than Dijkstra, which is the price you pay for tolerating negative weights. Space is O(V) for the distance array.

If you need the shortest path between every pair of nodes, reach for Floyd-Warshall instead — three nested loops over an adjacency matrix, trying each node k as an intermediate hop:

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

That is O(V³) time and O(V²) space, and like Bellman-Ford it handles negative edges (a negative entry on the diagonal afterward signals a negative cycle).

When to use / pitfalls

Practice