Bellman-Ford Algorithm

Bellman-Ford computes single-source shortest paths in graphs that may contain negative edge weights. By performing |V|−1 full relaxation passes over all edges, it guarantees correctness and can detect negative weight cycles via a final pass that still improves a distance.

Handles

Negative Weights

Works with w < 0

Passes

|V|-1

Sequential relaxations

Cycle Check

Final Pass

Detects negatives

When to Use Bellman-Ford

Graphs with negative edge weights (no requirement of non-negative)
Need to detect negative weight cycles reachable from source
Preparation for Johnson's algorithm (initial reweight phase)
Currency arbitrage / profit cycle detection (negative log weights)
Edge list processing where adjacency build is expensive

Core Idea

Initialize dist[source]=0 and all others to ∞. Repeatedly relax every edge (u,v,w): if dist[u] + w < dist[v], update dist[v]. After |V|−1 passes, all shortest paths (with at most |V|−1 edges) are found. A final pass that still improves some dist[v] reveals a negative weight cycle reachable from the source.

Algorithm Metrics

Time

O(V·E)

Space

O(V)

Neg Weights

Yes

Neg Cycles

Detects

Actions

Dive into Theory Try Simulation

Back: Dijkstra Algorithm Next:floyd-warshall