Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 25

The authors describe the problem of finding the all-pairs shortest paths. The authors point out that most of the algorithms will use adjacency matrix representation.

The authors provide an algorithm to compute all-pairs shortest paths which is similar to a matrix-multiplication problem and prove its running time to be .

The authors then provide Floyd Warshall algorithm and prove that it runs in time. The authors then provide an algorithm to compute transitive closure of a graph based on Floyd Warshall algorithm.

The authors then discuss Johnson's algorithm whose running time is . The algorithm first tries to remove all edges with negative weight by assigning a new set of weights to all the edges, a process called reweighting. The authors then prove the running time of the algorithm.