 |  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
Single-Source Shortest Paths
Glossary
| weight | of path p = ⟨v0, v1, . . . , vk⟩ is the sum of the weights of its constituent edges.
(See page 580)
| | | | | shortest path | A shortest path from vertex u to vertex v is defined as any path p with weight w(p) = δ(u, v).
(See page 580)
| | | | | single-source shortest-paths problem | given a graph G = (V, E), we want to find a shortest path from a given source vertex s ∈ V to each vertex v ∈ V.
(See page 581)
| | | | | predecessor | Given a graph G = (V, E), we maintain for each vertex v ∈ V a predecessor π[v] that is either another vertex or NIL.
(See page 584)
| | | | | shortest-paths tree | rooted at s, it is a directed subgraph G' = (V', E'), where V' ⊆ V and
E' ⊆ E, such that- V' is the set of vertices reachable from s in G,
- G' forms a rooted tree with root s, and
- for all v ∈ V', the unique simple path from s to v to G' is a shortest path from s to v in G.
(See page 584)
| | | | | relaxing | The process of relaxing an edge (u, v) consists of testing whether we can improve the shortest path to v found so far by going through u and, if so, updating d[v] and π[v].
(See page 585)
| | | | | triangle inequality | For any edge (u, v) ∈ E, we have δ(s, v) ≤ δ(s, u) + w(u, v).
(See page 587)
| | | | | upper-bound property | We always have d[v] ≥ δ(s, v) for all vertices v ∈ V, and once d[v] achieves the value of δ(s, v), it never changes.
(See page 587)
| | | | | no-path property | If there is no path from s to v, then we always have d[v] = δ(s, v) = ∞.
(See page 587)
| | | | | path-relaxation property | If p = ⟨v0, v1, . . . , vk⟩ is a shortest path from s = v0 to vk, and the edges of p are relaxed in the order (v0, v1), (v1, v2), . . . , (vk-1, vk), then d[vk] = δ(s, vk). This property holds regardless of any other relaxation steps that occur, even if they are itermixed with relaxations of the edges of p.
(See page 587)
| | | | | predecessor-subgraph property | Once d[v] = δ(s, v) for all v ∈ V, the predecessor subgraph is the shortest-paths tree rooted at s.
(See page 587)
| | | | | PERT chart | an acronym for "program evaluation and review technique."
(See page 594)
| | | | | critical path | longest path through the dag, corresponding to the longest time to perform an ordered sequence of jobs.
(See page 594)
| | | | | feasible solution | in linear programming, any vector x that satisfies Ax ≤ b, or to determine that no feasible solution exists.
(See page 601)
| | | | | arbitrage | the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency.
(See page 615)
| | | | | nests | A d-dimensional box with dimensions (x1, x2, . . . , xd) nests within another box with dimensions (y1, y2, . . . , yd) if there exists a permutation π on {1, 2, . . . , d} such that
xπ(1) < y1, xπ(2) < y2, . . . , xπ(d) < yd.
(See page 615)
| | | | | scaling | A scaling algorithm solves a problem by initially considering only the highest order bit of each relevant input value (such as an edge weight). It then refines the initial solution by looking at the two highest-order bits. It progressively looks at more and more high-order bits, refining the solution each time, until all bits have been considered and the correct solution has been computed.
(See page 616)
| | | | | bitonic | A sequence is bitonic if it monotonically increases and then monotonically decreases, or if it can be circularly shifted to monotonically increase and then monotonically decrease.
(See page 618)
|
|
2002 McGraw-Hill Higher Education