Johnson's algorithm is a way to solve the all pairs shortest path problem in a sparse weighted, directed graph.
First, it adds a new node with zero weight edge from it to all other nodes, and runs the Bellman-Ford algorithm to check for negative weight cycles and find h(v), the least weight of a path from the new node to node v. Next it reweights the edges using the nodes' h(v) values. Finally for each node, it runs Dijkstra's algorithm and stores the computed least weight to other nodes, reweighted using the nodes' h(v) values, as the final weight. The time complexity is
- O(V2log V + VE).
References
- "Johnson's Algorithm". AUTHOR(S), "Johnson's algorithm", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST. 14 June.
{{cite web}}: Check date values in:|date=and|year=/|date=mismatch (help)