Shortest Path: Bellman-Ford vs. Johnson

Question

I have difficulties in understanding the usefulness of the Johnson Algorithm. I think the question must sound really stupid for someone with knowledge in this area, but I cannot figure it out. According to Wikipedia, the Johnson Algorithm uses the Bellman Ford Algorithm to transform the weights of the edges to non-negative weights and then uses the Dijkstra Algorithm to find the shortest path. But the Bellman Ford Algorithm is also an algorithm to find the shortest path. Why don't we just use the shortest path that we get from the Bellman Ford Algorithm?

Answer 1

The Bellman-Ford algorithm finds the shortest path from a single source to all graph vertices ("single-source shortest paths"). Johnson's algorithm finds the shortest path from every vertex to every other vertex ("all-pairs shortest paths"), and so it is equivalent to running Bellman-Ford from every possible start vertex in your graph.

Answer 2

I know I am late to this party, but I just stumbled upon the question because I was just asking myself the same thing.

For better understanding I would like to point out that the first step of Johnson's Algorithm actually creates a new graph. It does this by cleverly using the Bellman-Ford algorithm to transform the original graph (which can have negative edges) into a different (but equivalent) graph that does not have negative edges. This new graph is now safe to be used with Dijkstra's Algorithm. Dijkstra's Algorithm is then used to efficiently calculate the "all-pairs shortest paths" that the two other answers mention.

A nice explanation can be found here: http://www.geeksforgeeks.org/johnsons-algorithm/