Bellman-Ford
DSA · Graphs
Theory
Bellman-Ford computes shortest paths from one source even when some edge weights are negative. It relaxes every edge V-1 times, because a shortest path can contain at most V-1 edges. A further round that still improves a distance proves there is a negative-weight cycle, where costs can be lowered forever. It runs in O(V × E), slower than Dijkstra.
Why we use it
It handles negative weights and detects negative cycles, which Dijkstra cannot.
When to use it
Use it for currency arbitrage detection, financial graphs with credits and debits, and routing protocols such as RIP.
How it works
- dist[source] = 0, others infinity
- Repeat V - 1 times: relax every edge
- Run one more pass over all edges
- Any distance still improves? Yes: Negative cycle exists. No: Distances are final.
- Done
Syntax
dist[src] = 0
repeat V-1 times:
for (u, v, w) in edges:
if dist[u] + w < dist[v]: dist[v] = dist[u] + w
one more pass improves anything -> negative cycle
Time: O(V·E)Example
vertices = ["A", "B", "C", "D"]
edges = [("A", "B", 4), ("A", "C", 5), ("B", "C", -3), ("C", "D", 4), ("B", "D", 6)]
def bellman_ford(src):
dist = {v: float("inf") for v in vertices}
dist[src] = 0
for _ in range(len(vertices) - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None
return dist
print("Shortest distances:", bellman_ford("A"))
edges.append(("D", "B", -5))
print("With a negative cycle:", bellman_ford("A"))Key points
- Works with negative weights
- Relax all edges V-1 times
- Extra improvement means a negative cycle
- O(V·E): slower than Dijkstra