Bellman-Ford Algorithm

#How does it work?

Bellman-Ford finds shortest paths from a start node to every node, like Dijkstra, but it also works with negative edge weights. Negative weights model refunds, discounts or energy gains.

Once Dijkstra settles a node it never looks at it again. A negative edge can make a settled node cheaper to reach later, so Dijkstra gives wrong answers. In the example graph Dijkstra says dist[3] = 2, but the path 1 → 2 → 3 costs 4 + (−3) = 1.

Bellman-Ford isn't greedy: it relaxes every edge again and again for V − 1 rounds. A shortest path has at most V − 1 edges, so after round i every shortest path of at most i edges is correct.

If a distance still improves in an extra V-th round, the graph has a negative cycle: going round it keeps lowering the cost, so shortest paths are undefined. Bellman-Ford can detect this.

#Try it yourself

#Step by step

1. 01Set dist[start] = 0 and every other distance to ∞.
2. 02For V − 1 rounds: for every edge u → v, if dist[u] + w < dist[v], update dist[v].
3. 03If a round changes nothing, stop early.
4. 04Finally try one more round: if a distance still drops, there is a negative cycle.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

INF = float("inf")

# Directed edges (from, to, weight); two of them are negative.
EDGES = [(1, 2, 4), (1, 3, 2), (2, 3, -3), (2, 4, 2), (3, 5, 3),
         (3, 6, 5), (4, 7, 2), (5, 4, -1), (5, 7, 4), (6, 7, 1)]
N = 7


def bellman_ford(edges, start):
    """Returns (dist, prev), or None if a negative cycle is reachable."""
    dist = {v: INF for v in range(1, N + 1)}
    prev = {}
    dist[start] = 0
    for _ in range(N - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed:
            break  # nothing will change in later rounds either
    for u, v, w in edges:  # one more round: still improving means a negative cycle
        if dist[u] + w < dist[v]:
            return None
    return dist, prev


dist, prev = bellman_ford(EDGES, 1)
print(" ".join(str(dist[v]) for v in range(1, N + 1)))

path = [7]
while path[-1] != 1:
    path.append(prev[path[-1]])
print(" ".join(map(str, reversed(path))))  # uses both negative edges

print("negative cycle" if bellman_ford(EDGES + [(7, 5, -6)], 1) is None else "ok")  # 5 -> 7 -> 5 weighs -2

#Complexity

Each round goes through every edge and up to V − 1 rounds are needed, so it is slower than Dijkstra's O((V + E) log V). Without negative edges, prefer Dijkstra. SPFA, a queue-based refinement, is faster on average but has the same worst case.

#When to use it?

Shortest paths with negative weights, detecting currency arbitrage (a negative cycle over the logarithms of exchange rates), distance-vector routing protocols (RIP) and the first step of Johnson's algorithm use Bellman-Ford.

#Practice

Log in to answer questions and save your progress.