Search code examples
time-complexityshortest-pathdijkstrabellman-fordfloyd-warshall

Why would one consider using Bellman Ford?


So, say you wanted to find the shortest path between two vertices. I would argue this:

A.) If the graph has no negative edge weights and is represented by an adjacency list, you could run Dijkstra's algorithm either once to find a single source shortest path in O(V^2) time or run Dijkstra's algorithm on all vertices O(V^3) (both of are pretty sloppy in the case of non-complete graphs) to find all shortest paths.

B.) Graph with no negative edge weights and is in matrix form: Either use Dijkstra's to find a single source shortest path O(V^2) or run Floyd-Warshall to find all possible shortest paths O(V^3).

C.) Graph has negative edge weights and is in either list or matrix form: Run either Bellman-Ford to find the single source shortest path O(V^3) or use FW to find all shortest paths in O(V^3) time. Since their runtime is approximately the same (they will differ if the graph is in list form) you might as well just run FW and get more information for approximately the same runtime... right?

So: Is there any real-world application where one would use Bellman-Ford? The only thing I can think of is if the graph is in list form and has negative edge weights. I'm not sure of the implications this has on FW or if that list would first need to be converted into a matrix.


Solution

  • Technically, even in case of graph with negative weights, give -N the minimum cost registered, you could increase all the weights by N (in order to make the most negative weight equal to zero). Then you can apply Dijkstra or any other algorithm. The shortest path doesn't change. Just remember to readjust the weights before computing the real shortest path's cost