 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
All-Pairs Shortest Paths
Chapter Overview - Chapter 25| Section 25.1 presents a dynamic-programming algorithm based on matrix multiplication to solve the all-pairs shortest-path problem. Using the technique of "repeated squaring", this algorithm can be made to run in Θ(V3 lg V) time. Another dynamic-programming algorithm, the Floyd-Warshall algorithm, is given in Section 25.2. The Floyd-Warshall algorithm runs in time Θ(V3). Section 25.2 also covers the problem of finding the transitive closure of a directed graph, which is related to the all-pairs shortest-path 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 shortest-paths problem in O(V2 lg V + VE) time, which makes it a gook 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 wij, lij, or dij. Some matrices will have parenthesized lowercase superscripts, as in L(m) = (lij(m)) or D(m) = (dij(m)), 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].
|
|
2002 McGraw-Hill Higher Education