BellmanFord Algorithm

suggest change

Remarks

Given a directed graph G, we often want to find the shortest distance from a given node A to the rest of the nodes in the graph. Dijkstra's algorithm is the most famous algorithm for finding the shortest path, but it works only if the edge weights are non-negative. Bellman-Ford aims to find the shortest path from a given node (if one exists) even if some of the weights are negative. A shortest distance may not exist if a negative cycle is present, because walking around that cycle makes the total distance arbitrarily small. Bellman-Ford can also detect such a cycle.

The algorithm runs in O(V*E) time, where V is the number of vertices and E is the number of edges.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents