Bellman-Ford Algorithm

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.