algorithm Bellman–Ford Algorithm
Remarks
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
