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 in which some of the edge weights may be negative numbers, but no negative-weight cycles exist.

It consists of the following steps:

1. First, it adds a new node q to the graph, with a zero weight edge connecting q to each other node.
2. Second, it runs the Bellman-Ford algorithm, starting from the new vertex q, to check for negative weight cycles and to find for each vertex v the least weight h(v) of a path from q to v.
3. Next it reweights the edges of the original graph using the values computed by the Bellman-Ford algorithm: an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) −h(v).
4. Finally, for each node s, it runs Dijkstra's algorithm to find the shortest paths from s to each other vertex in the graph, using these modified weights to measure the length of each path.

In the reweighted graph, all paths between a pair s and t of nodes have the same quantity h(s) -h(t) added to them, so a path that is shortest in the original graph remains shortest in the modified graph and vice versa. However, due to the way the values h(v) were computed, all modified edge lengths are non-negative. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.

The time complexity of this algorithm, using Fibonacci heaps in the implementation of Dijkstra's algorithm, is O(V²log V + VE): the algorithm uses O(VE) time for the Bellman-Ford stage of the algorithm, and O(V log V + E) for each of V instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the Floyd-Warshall algorithm, which solves the same problem in time O(V³).

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". Paul E. Black, "Johnson's algorithm", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST. {{cite web}}: Unknown parameter |accessdaymonth= ignored (help); Unknown parameter |accessyear= ignored (|access-date= suggested) (help)
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.