Given a directed graph `G`

, we often want to find the shortest distance from a given node `A`

to rest of the nodes in the graph. **Dijkstra** algorithm is the most famous algorithm for finding the shortest path, however it works only if edge weights of the given graph are non-negative. **Bellman-Ford** however aims to find the shortest path from a given node (if one exists) even if some of the weights are negative. Note that, shortest distance may not exist if a negative cycle is present in the graph (in which case we can go around the cycle resulting in infinitely small total distance ). **Bellman-Ford** additionally allows us to determine the presence of such a cycle.

Total complexity of the algorithm is `O(V*E)`

, where V - is the number of vertices and `E`

number of edges

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow