Johnson's Algorithm For Sparse Graphs

Johnson's algorithm finds shortest paths between all pairs in $O(V^2lgV + VE)$ time. Johnson's uses both Dijkstra and BF as subroutines. It uses the technique of reweighting, which works as follows. If all edge weights w in a graph G=(V,E) are nonnegative, we can find shortest path between all pairs of vertices by running Dijkstra once from each vertex; with the Fibonacci-heap min-priority queue, the running time of this all-pairs algorithm is $O(V^2lgV + VE)$. If G has negative-weight edges but no negative cycles, we simply compute a new set of nonnegative edge weights that allows us to use the same method. The new set of edge weights $w^-$ must satisfy two important properties: