Bellman-Ford Algorithm

The Bellman-Ford algorithm is a single-source shortest path algorithm that can handle graphs with negative edge weights, unlike Dijkstra's algorithm, which requires non-negative weights. Developed by Richard Bellman and Lester Ford in the 1950s, it operates through a process of iterative relaxation: for a graph with V vertices, it relaxes all edges V-1 times, progressively refining distance estimates until they converge to the true shortest paths. A final pass through all edges detects negative-weight cycles — loops whose total weight is negative, making shortest paths undefined because one could loop indefinitely to decrease cost.

The algorithm's greater generality comes at a cost: its time complexity is O(V * E), compared to Dijkstra's O((V + E) log V) with a priority queue. For dense graphs, this is a significant slowdown. Yet Bellman-Ford remains indispensable in domains where negative weights naturally arise: currency arbitrage detection (where exchange rates can create negative cycles representing profitable loops), traffic routing with toll rebates, and certain formulations of difference constraints in constraint satisfaction problems.

The relaxation procedure itself is elegant in its simplicity. Each edge (u, v) with weight w is examined, and if the current distance estimate to v can be improved by going through u, it is updated. This local improvement rule, applied globally and repeatedly, converges to a globally optimal solution — a property that holds even when the local rule temporarily worsens some estimates before the global structure becomes apparent. Bellman-Ford thus illustrates a principle that recurs throughout dynamic programming: optimal substructure permits global optimization through local operations, provided the operations are applied in the right order and for sufficient iterations.

Bellman-Ford is not merely a slower Dijkstra. It is a different conceptual tool, designed for a different class of problems — problems where the path itself can improve by going backward, and where the absence of negative cycles is a theorem to be verified rather than an assumption to be made.