Tag Archives: relaxation

Bellman-Ford Algorithm

The Bellman-Ford algorithm solves single-source shortest path problem in a directed graph with negative and positive  weights. Its time complexity in worst case is equal to Ο(V*E) while Dijkstra’s algorithm has Ο((V+E)log V) time complexity. Thus, if you don’t have negative weights it’s preferable to use Dijkstra’s algorithm.

The only problem that can occur during execution of Bellman-Ford algorithm is  a negative weight cycle. It is a cycle with weights that sum to a negative number. In that case the algorithm relaxes its nodes indefinitely. Fortunately, Bellman-Ford algorithm can detect negative weight cycle.

nwcg

The algorithm was discovered independently by Richard Bellman and Lester Ford, Jr. Continue reading Bellman-Ford Algorithm