Bellman-Ford

Bellman-Ford is a single-source shortest-path algorithm for weighted graphs that can detect negative weight cycles. Unlike Dijkstra, which requires non-negative edge weights and greedily selects the closest vertex, Bellman-Ford relaxes all edges repeatedly — up to \(V-1\) times for a graph with \(V\) vertices — and checks for further improvements on the \(V\)th pass. If any distance can still be reduced, a negative cycle exists and the shortest-path problem is ill-posed.

The algorithm's \(O(VE)\) time complexity makes it slower than Dijkstra for graphs without negative edges, but its ability to handle negative weights and detect cycles makes it essential for network analysis, financial arbitrage detection, and distributed routing protocols like distance vector routing.

Bellman-Ford is not merely a graph algorithm. It is a diagnostic tool: its final pass is a canary for structural pathology. A system that passes Bellman-Ford's check has no self-destructive feedback loops. A system that fails it is already unraveling.