Johnson's algorithm

Template:Tree search algorithm

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).

See also

• Floyd-Warshall algorithm

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 14 June. {{cite web}}: Check date values in: |accessdate= (help); Unknown parameter |accessyear= ignored (|access-date= suggested) (help)