Geek asks and answers

The Shortest Way: Bellman Ford vs. Johnson

I find it difficult to understand the usefulness of Johnson Algorithm . I think the question should sound really stupid for someone who has knowledge in this area, but I cannot understand it. According to Wikipedia, the Johnson Algorithm uses the Bellman Ford Algorithm to convert edge weights to non-negative weights, and then uses Dijkstra's algorithm to find the shortest path. But the Bellman Ford Algorithm is also a shortest path search algorithm. Why don't we use the shortest path we get from the Bellman Ford Algorithm?

+3
source share
3 answers

The Bellman-Ford algorithm finds the shortest path from one source to all the vertices of the graph ("shortest paths with one source"). Johnson's algorithm finds the shortest path from each vertex to every other vertex (the “shortest paths of all pairs”), and therefore it is equivalent to running Bellman-Ford from all possible starting vertices on your graph.

+7
source

The Bellman Ford algorithm is used to find the shortest path from one vertex (source) to all other vertices, while the Johnson algorithm is used to find the entire shortest path of a pair. If you want to implement Johnson's algorithm in C, let me know.

0
source

, , , .

, . , -, ( ) ( ) , . . Dijkstra Algorithm " ", .

: http://www.geeksforgeeks.org/johnsons-algorithm/

0

More articles:


All Articles