Johnson's algorithm

From Wikipedia, the free encyclopedia

Categories: Graph algorithms | Computer science stubs

Graph search algorithms
Search A* B* Bellman-Ford algorithm Best-first search Bidirectional search Breadth-first search Depth-first search Depth-limited search Dijkstra's algorithm Floyd-Warshall algorithm Hill climbing Iterative deepening depth-first search Johnson's algorithm Uniform-cost search

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(V²log V + VE).

References

Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24(1):1–13, January 1977. doi:10.1145/321992.321993
Johnson's Algorithm. AUTHOR(S), "Johnson's algorithm", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.. Retrieved on 14 June, 2005.