Content deleted Content added
m Signing comment by 96.57.23.82 - "" |
No edit summary |
||
Line 95:
Since it quotes the article, it is not surprising that it is hard to understand. As it is, it is clear. The algorithm in the code doesn't match diagram, and the diagram doesn't match the text. This whole article needs a rewrite. Perhaps the esteemed Professor of Univ Irvine can donate his class notes. <small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/96.57.23.82|96.57.23.82]] ([[User talk:96.57.23.82|talk]]) 01:41, 17 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
Follow Cormen if you need to
The structure of a shortest path
In the Floyd-Warshall algorithm, we use a different characterization of the structure of a shortest path than we
used in the matrix-multiplication-based all-pairs algorithms. The algorithm considers the "intermediate" vertices of
a shortest path, where an intermediate vertex of a simple path p = 〈 v , v , . . . , v 〉 is any vertex of p other than
1 2 lv or v , that is, any vertex in the set {v ,v , . . . , v }.
1 l 2 3 l-1The Floyd-Warshall algorithm is based on the following observation. Let the vertices of G be V = {1, 2, . . . ,
n}, and consider a subset {1, 2, . . . , k} of vertices for some k. For any pair of vertices i, j ∈ V, consider all
paths from i to j whose intermediate vertices are all drawn from {1, 2, . . . , k}, and let p be a minimum-weight
path from among them. (Path p is simple, since we assume that G contains no negative-weight cycles.) The
Floyd- Warshall algorithm exploits a relationship between path p and shortest paths from i to j with all
intermediate vertices in the set {1, 2, . . . , k - 1}. The relationship depends on whether or not k is an
intermediate vertex of path p.
Figure 26.3 Path p is a shortest path from vertex i to vertex j, and k is the highest-numbered intermediate vertex of p.
Path p1 , the portion of path p from vertex i to vertex k, has all intermediate vertices in the set {1, 2, . . . , k – 1}. The
same holds for path p2 from vertex k to vertex j.
•
If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set {1, 2, . . . ,
k – 1}. Thus, a shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2, . . . ,
k – 1} is also a shortest path from i to j with all intermediate vertices in the set {1, 2, . . . , k}.
•
If k is an intermediate vertex of path p, then we break p down into
as shown in Figure 26.3
. By Lemma 25.1, p1 is a shortest path from i to k with all intermediate vertices in the set {1, 2, . . . ,
k}. In fact, vertex k is not an intermediate vertex of path p1 , and so p1 is a shortest path from i to
k with all intermediate vertices in the set {1, 2, . . . , k - 1}. Similarly, p2 is a shortest path from vertex
k to vertex j with all intermediate vertices in the set {1, 2, . . . , k - 1}.
A recursive solution to the all-pairs shortest-paths problem
Based on the above observations, we define a different recursive formulation of shortest-path estimates than we did
in Section 26.1. Let
be the weight of a shortest path from vertex i to vertex j with all intermediate vertices in
the set {1, 2, . . . , k}. When k = 0, a path from vertex i to vertex j with no intermediate vertex numbered higher
than 0 has no intermediate vertices at all. It thus has at most one edge, and hence
. A recursive definition
is given by
(26.5)
The matrix
gives the final answer—
are in the set {1, 2, . . . , n}.
for all i, j ∈ Vbecause all intermediate vertices
Computing the shortest-path weights bottom up
Based on recurrence (26.5), the following bottom-up procedure can be used to compute the values
in order of
increasing values of k. Its input is an n × n matrix W defined as in equation (26.1). The procedure returns the matrix
D(n) of shortest-path weights.
Figure 26.4 shows a directed graph and the matrices D (k) computed by the Floyd-Warshall algorithm.
The running time of the Floyd-Warshall algorithm is determined by the triply nested for loops of lines 3-6. Each
execution of line 6 takes O(1) time. The algorithm thus runs in time Θ(n3). As in the final algorithm in Section 26.1
, the code is tight, with no elaborate data structures, and so the constant hidden in the Θ -notation is small. Thus, the
Floyd-Warshall algorithm is quite practical for even moderate-sized input graphs.
Constructing a shortest path
There are a variety of different methods for constructing shortest paths in the Floyd-Warshall algorithm. One way
is to compute the matrix D of shortest-path weights and then construct the predecessor matrix Π from the
D matrix. This method can be implemented to run in O(n3 ) time (Exercise 26.1-5). Given the predecessor matrix
Π, the PRINT- ALL- PAIRS- SHORTEST- PATH procedure can be used to print the vertices on a given shortest path.
We can compute the predecessor matrix Π "on-line" just as the Floyd-Warshall algorithm computes the
matrices D (k) . Specifically, we compute a sequence of matrices Π(0) , Π(1) , . . . , Π(n), where Π = Π(n) and
is
defined to be the predecessor of vertex j on a shortest path from vertex i with all intermediate vertices in the set
{1, 2, . . . , k}.
We can give a recursive formulation of
vertices at all. Thus,
. When k = 0, a shortest path from i to j has no intermediate
Figure 26.4 The sequence of matrices D (k) and Π(k) computed by the Floyd-Warshall algorithm for the graph in Figure 26.1
.
| |||