Comparison
Compared to the Dijkstra Algorithm:
- Bellman-Ford can handle negative weights whereas Dijkstra can only handle positives.
- Dijsktra's algorithm Time Complexity: O(V^2)
- Bellman Ford Time Complexity: O(V^3)
Dijkstra Running Cases:
- Worst Case O(|E|+|V|log|V|)
Bellman Ford Running Cases:
Best Case O(|E|)
Worst Case O(|V||E|)
Algorithm Psuedocode
Explanation
Application
Routing information protocol
CPU Gate
Background
Richard E. Bellman
- The people:
- First proposed by Alfonso Shimbel in 1955
- Published by Lester Ford in 1956 and by Richard Bellman in 1958
- Also by Edward F. Moore in 1957
- What does it do?
- Bellman-Ford is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph
- Why?
- created to find the shortest path when there is a negative cycle in a graph
Lester Ford Jr.
Bellman-Ford Algorithm
By: Eunice Arokiadoss and Fehmina Hasan