Bellman Ford is another single source shortest path algorithm. We have discussed Dijkstra here in CommonLounge before.
The most important questions are:
- 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.
- Why don’t we use Bellman Ford and forget about Dijkstra?
- Bellman Ford is slower than Dijkstra. It runs in O(V*E).
- 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.
This tutorial by Tushar Roy is a detailed one, explaining bellman ford and running a demo himself on the board.
This second tutorial is a shorter video tutorial by Algorithms With Attitude.