CommonLounge Archive

Single Source Shortest Path: Bellman Ford

May 27, 2017

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?
  2. Bellman Ford supports finding shortest path in graphs with negative weight edges. (Dijkstra doesn’t).
  3. Bellman Ford can find negative weight cycles in graphs.
  4. Why don’t we use Bellman Ford and forget about Dijkstra?
  5. Bellman Ford is slower than Dijkstra. It runs in O(V*E).
  6. What are the most important applications of Bellman Ford other than just handling negative weight edges and checking negative cycles
  7. Bellman Ford is a very useful algorithm as it’s a part of MinCost MaxFlow algorithms.
  8. Bellman Ford can be used to solve a system of linear inequalities.

Video tutorial - I

This tutorial by Tushar Roy is a detailed one, explaining bellman ford and running a demo himself on the board.

Video tutorial - II

This second tutorial is a shorter video tutorial by Algorithms With Attitude.

Further Reading

  1. Text tutorials: The text tutorial on Brilliant is quite nice.
  2. Exercise With Hints : UVA 11721 Instant View Of Big Bang

© 2016-2022. All rights reserved.