BellmanFord Algorithm
suggest changeRemarks
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.
Found a mistake? Have a question or improvement idea?
Let me know.
Table Of Contents