Bellman Ford is another single source shortest path algorithm. We have discussed Dijkstra here in CommonLounge before.
The most important questions are:
1) What is special about Bellman Ford? When to use it and avoid Dijkstra?
- Bellman Ford supports finding shortest path in graphs with negative weight edges. (Dijkstra doesn't).
- Bellman Ford can find negative weight cycles in graphs.
2) Why don't we use Bellman Ford and forget about Dijkstra?
- Bellman Ford is slower than Dijkstra. It runs in O(V*E).
3) What are the most important applications of Bellman Ford other than just handling negative weight edges and checking negative cycles
- Bellman Ford is a very useful algorithm as it's a part of MinCost MaxFlow algorithms.
- Bellman Ford can be used to solve a system of linear inequalities.
