Chapter notes

Lawler [196] has a good discussion of the all-pairs shortest-paths problem, although he does not analyze solutions for sparse graphs. He attributes the matrix-multiplication algorithm to the folklore. The Floyd-Warshall algorithm is due to Floyd [89], who based it on a theorem of Warshall [308] that describes how to compute the transitive closure of boolean matrices. Johnson's algorithm is taken from [168].

Several researchers have given improved algorithms for computing shortest paths via matrix multiplication. Fredman [95] shows that the all-pairs shortest paths problem can be solved using O(V^5/2) comparisons between sums of edge weights and obtains an algorithm that runs in O(V³(lg lg V/ lg V)^1/3) time, which is slightly better than the running time of the Floyd-Warshall algorithm. Another line of research demonstrates that algorithms for fast matrix multiplication (see the chapter notes for Chapter 28) can be applied to the all-pairs shortest paths problem. Let O(n^w) be the running time of the fastest algorithm for multiplying n × n matrices; currently w < 2.376 [70]. Galil and Margalit [105, 106] and Seidel [270] designed algorithms that solve the all-pairs shortest paths problem in undirected, unweighted graphs in (V^w p(V)) time, where p(n) denotes a particular function that is polylogarithmically bounded in n. In dense graphs, these algorithms are faster than the O(V E) time needed to perform |V| breadth-first searches. Several researchers have extended these results to give algorithms for solving the all-pairs shortest paths problem in undirected graphs in which the edge weights are integers in the range {1, 2,.., W}. The asymptotically fastest such algorithm, by Shoshan and Zwick [278], runs in time O(W V^w p(V W)).

Karger, Koller, and Phillips [170] and independently McGeoch [215] have given a time bound that depends on E*, the set of edges in E that participate in some shortest path. Given a graph with nonnegative edge weights, their algorithms run in O(V E*+V² lg V) time and are improvements over running Dijkstra's algorithm |V| times when |E*| = o(E).

Aho, Hopcroft, and Ullman [5] defined an algebraic structure known as a "closed semiring," which serves as a general framework for solving path problems in directed graphs. Both the Floyd-Warshall algorithm and the transitive-closure algorithm from Section 25.2 are instantiations of an all-pairs algorithm based on closed semirings. Maggs and Plotkin [208] showed how to find minimum spanning trees using a closed semiring.