Shortest PathO(V · E)· Level 04

Bellman-Ford

Shortest paths with negative edge weights & cycle detection.

Intuition

Where Dijkstra is greedy, Bellman-Ford is patient. It relaxes every edge V−1 times, guaranteeing correctness even with negative edges. A V-th relaxation that still improves a distance proves a negative cycle exists.

Step-by-step

1
Initialise `dist[s] = 0`, all others `∞`.
2
Repeat V−1 times: for every edge (u,v,w), relax if `dist[u] + w < dist[v]`.
3
Run one more pass — if any edge still relaxes, there's a negative-weight cycle reachable from `s`.

Pseudocode

pseudocode

BELLMAN_FORD(G, s):
  dist[v] = INF; dist[s] = 0
  repeat |V|-1 times:
    for each edge (u,v,w):
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
  for each edge (u,v,w):
    if dist[u] + w < dist[v]:
      report "negative cycle"

Implementation (Python)

python

def bellman_ford(vertices, edges, start):
    dist = {v: float('inf') for v in vertices}
    dist[start] = 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]:
            raise ValueError("Negative cycle detected")

    return dist

Real-world applications

Currency arbitrage detection
Distance-vector routing protocols (RIP)
Constraint systems with negative penalties