Shortest Path: Bellman-Ford vs. Johnson

I have difficulties in understanding the usefulness of the Johnson Algorithm. I think the question must sound really stupi开发者_Go百科d 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?

---

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.

---

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/

---

The Bellman Ford algorithm is used for finding the shortest path from single vertex(source) to all other vertices whereas Johnson algorithm is used to find all pair shortest path.If you want implementation of Johnson algorithm in C,inform me.