McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
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

Glossary


predecessor matrix  To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor matrix Π = (Πij), where Πij is NIL if either i = j or there is no path from i to j, and otherwise Πij is the predecessor of j on some shortest path from i.
(See page 621)
predecessor subgraph  For each vertex i ∈ V, we define the predecessor subgraph of G for i as Gπ,i = (Vπ, i, Eπ, i), where

Vπ, i = {j ∈ V : πij ≠ NIL} ∪ {i}

and

Eπ,i = {(πij, j) : j ∈ Vπ,i - {i}}.


(See page 621)
Floyd-Warshall algorithm  algorithm resulting from use of a different dynamic-programming formulation to solve the all-pairs shortest-patsh problem on a directed graph G = (V, E). Negative-weight edges may be present, but it assumes that there are no negative-weight cycles.
(See page 629)
intermediate  The Floyd-Warshall algorithm considers the "intermediate" vertices of a shortest-path, where an intermediate vertex of a simple path
p = ⟨v1, v2, . . . , vl⟩ is any vertex of p other than v1 or vl, that is, any vertex in the set {v2, v3, . . . , vl-1}.
(See page 629)
transitive closure  The transitive closure of G is defined as the graph G* = (V, E*), where E* = {(i, j) : there is a path from vertex i to vertex j in G}.
(See page 632)
reweighting  a technique which works as follows: If all edge weights w in a graph
G = (V, E) are nonnegative, we can find shortest paths between all pairs of vertices by running Dijkstra's algorithm once from each vertex; with the Fibonacci-heap min-priority queue, the running time of this all-pairs algorithm is O(V2 lg V + VE). If G has negative-weight edges but no negative-weight cycles, we simply compute a new set of nonnegative edge weights that allows us to use the same method.
(See page 636)
ε-dense  A graph G = (V, E) is ε-dense if |E| = Θ(V1+ε) for some constant ε inthe range 0 < ε ≤ 1.
(See page 641)








Copyright2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.