Chapter outline

Section 25.1 presents a dynamic-programming algorithm based on matrix multiplication to solve the all-pairs shortest-paths problem. Using the technique of "repeated squaring," this algorithm can be made to run in Θ(V³ lg V) time. Another dynamic-programming algorithm, the Floyd-Warshall algorithm, is given in Section 25.2. The Floyd-Warshall algorithm runs in time Θ(V³). Section 25.2 also covers the problem of finding the transitive closure of a directed graph, which is related to the all-pairs shortest-paths problem. Finally, Section 25.3 presents Johnson's algorithm. Unlike the other algorithms in this chapter, Johnson's algorithm uses the adjacency-list representation of a graph. It solves the all-pairs shortestpaths problem in O(V² lg V + V E) time, which makes it a good algorithm for large, sparse graphs.

Before proceeding, we need to establish some conventions for adjacency-matrix representations. First, we shall generally assume that the input graph G = (V, E) has n vertices, so that n = |V|. Second, we shall use the convention of denoting matrices by uppercase letters, such as W , L, or D, and their individual elements by subscripted lowercase letters, such as W_ij, l_ij, or d_ij. Some matrices will have parenthesized superscripts, as in or , to indicate iterates. Finally, for a given n × n matrix A, we shall assume that the value of n is stored in the attribute rows[A].