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.

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