🎓 A1Learner
🔍

DSA Bellman–Ford

Bellman–Ford finds shortest paths in directed graphs whose edges may carry negative weights. It tries to improve every edge many times over, and one extra pass exposes any negative cycle.

One relaxation

Relaxing the edge from A tries the stored distance of A plus the edge weight. The sum 4 beats the stored 99 in one test.

dist = {"A": 0, "B": 10, "C": 99}
u, v, w = "A", "C", 4
print("before:", dist[v])
if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    print("relaxed:", u, "->", v, "now", dist[v])

Passes settle the distances

Each pass relaxes every edge once in list order. Pass one settles this chain, and pass two changes nothing.

edges = [(0, 1, 5), (1, 2, -2), (0, 2, 10)]
n = 3
dist = [0, 99, 99]
for p in range(n - 1):
    changed = 0
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            changed += 1
    print("pass", p + 1, "improvements:", changed, "dist:", dist)

One pass too many

The cycle in this graph totals minus one. A third pass still improves a distance, which exposes the cycle.

edges = [(0, 1, 1), (1, 2, -3), (2, 0, 1)]
n = 3
dist = [0, 99, 99]
for p in range(n - 1):
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
print("after n-1 passes:", dist)
for u, v, w in edges:
    if dist[u] + w < dist[v]:
        print("pass", n, "still improves", u, "->", v)
        print("verdict: negative cycle")
        break

Example

def bellman_ford(n, edges, source):
    dist = [10 ** 9] * n
    dist[source] = 0
    tried = 0
    improved = 0
    for p in range(n - 1):
        for u, v, w in edges:
            tried += 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                improved += 1
        print("pass", p + 1, "dist:", dist)
    for u, v, w in edges:
        tried += 1
        if dist[u] + w < dist[v]:
            return dist, tried, improved, True
    return dist, tried, improved, False


edges = [(0, 1, -1), (0, 2, 4), (1, 2, 3), (1, 3, 2),
         (1, 4, 2), (3, 2, 5), (3, 1, 1), (4, 3, -3)]
dist, tried, improved, cycle = bellman_ford(5, edges, 0)
print("shortest distances from 0:", dist)
print("relaxations tried:", tried, "improved:", improved)
print("negative cycle:", cycle)

bad = [(0, 1, 1), (1, 2, -3), (2, 1, 1)]
dist, tried, improved, cycle = bellman_ford(3, bad, 0)
print("second graph distances:", dist)
print("relaxations tried:", tried, "improved:", improved)
print("negative cycle:", cycle)

Key points

  • Relaxing an edge means trying the route through its start to improve the stored distance of its end.
  • A negative cycle is a directed loop whose total weight is below zero.
  • After pass k, every shortest path that uses at most k edges is final.
  • A shortest path without loops uses at most n minus 1 edges.
  • So n minus 1 passes always suffice when no negative cycle exists.
  • Any improvement during pass n means a negative cycle feeds that route.

In this example, the first graph settles in its first pass. Its distances are 0, minus 1, 2, minus 2 and 1. Four passes plus the detection pass try forty relaxations, and six of them succeed. The second graph keeps improving during its detection pass after only eight tries. Its verdict is a negative cycle, so no shortest paths exist for it.

Note

Dijkstra's greedy choice breaks under negative edges, but repeated relaxing does not.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A graph has 6 nodes and no negative cycle. How many full passes guarantee the shortest distances?