BellmanFord

Bellman-Ford is a graph search algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted directed graph. It can handle graphs with negative edge weights and can also detect the presence of negative-weight cycles reachable from the source. The algorithm is named after Richard Bellman and Lester Ford, Jr., who developed and published it in the 1950s.

The method initializes the distance to the source as zero and to all other vertices as infinity. It then relaxes each edge in a series of passes. Specifically, for |V|−1 iterations, it examines every edge (u, v) with weight w and updates d[v] to min(d[v], d[u] + w) if a shorter path is found. A predecessor array may be maintained to reconstruct paths. After the |V|−1 iterations, a final pass checks whether any edge can still be relaxed; the existence of such an edge indicates a reachable negative-weight cycle.

Bellman-Ford runs in O(VE) time and O(V) space, where V is the number of vertices and E the number of edges. It is robust to negative weights, but if a negative cycle is reachable from the source, the algorithm cannot produce finite shortest-path values for the affected vertices. Variants like the queue-based SPFA (Shortest Path Faster Algorithm) exist and can perform faster in practice on many graphs, though without worst-case guarantees. Bellman-Ford is commonly used as a baseline in contexts where negative weights are present or when a simple, predictable algorithm is desired.