The Bellman-Ford Algorithm

The Bellman-Ford algorithm is a single-source shortest-paths algorithm discovered a few years before Dijkstra’s algorithm. Despite being slower than Dijkstra’s algorithm, it does have the following added advantages over it:

• It works correctly in the presence of negative-weight edges and computes the shortest paths as long as they are well-defined.welldefined

• If there’s a negative-weight cycle in the digraph that can be reached from the source vertex, Bellman-Ford has a way to detect this and alert the end user to the fact that the shortest-paths problem is not well-defined for the input digraph.

It’s interesting to know that the algorithm was discovered by Alfonso Shimbel in 1955 but is actually named after Richard Bellman and Lester Ford Jr., who also discovered the algorithm independently in 1958 and 1956, respectively.