chap26.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

Show how to express the single-source shortest-paths problem as a product of matrices and a vector. Describe how evaluating this product corresponds to a Bellman-Ford-like algorithm (see Section 25.3).<P>
<a name="08e0_1851">26.1-5<a name="08e0_1851"><P>
Suppose we also wish to compute the vertices on shortest paths in the algorithms of this section. Show how to compute the predecessor matrix <img src="../images/piuc.gif"> from the completed matrix <I>D</I> of shortest-path weights in <I>O</I>(<I>n</I><SUP>3</SUP>) time.<P>
<a name="08e0_1852">26.1-6<a name="08e0_1852"><P>
The vertices on shortest paths can also be computed at the same time as the shortest-path weights. Let us define <img src="558_a.gif"> to be the predecessor of vertex <I>j</I> on any minimum-weight path from<I> i</I> to <I>j</I> that contains at most <I>m</I> edges. Modify <FONT FACE="Courier New" SIZE=2>EXTEND</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT> and <FONT FACE="Courier New" SIZE=2>SLOW</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT> to compute the matrices <img src="../images/piuc.gif"><SUP>(1)</SUP>, <img src="../images/piuc.gif"><SUP>(2)</SUP>, . . . , <img src="../images/piuc.gif"><SUP>(<I>n-</I>1)</SUP> as the matrices <I>D</I><SUP>(1)</SUP>, <I>D</I><SUP>(2)</SUP>, . . . , <I>D</I><SUP>(<I>n</I>-1)</SUP> are computed.<P>
<a name="08e0_1853">26.1-7<a name="08e0_1853"><P>
<a name="08e0_1849">The <FONT FACE="Courier New" SIZE=2>FASTER</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS</FONT> procedure, as written, requires us to store <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg(<I>n</I> - 1)<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> matrices, each with <I>n</I><SUP>2</SUP> elements, for a total space requirement of <img src="../images/bound.gif">(<I>n</I><SUP>2 </SUP>lg <I>n</I>). Modify the procedure to require only <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) space by using only two <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrices.<P>
<a name="08e0_1854">26.1-8<a name="08e0_1854"><P>
<a name="08e0_184a"><a name="08e0_184b">Modify <FONT FACE="Courier New" SIZE=2>FASTER</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATHS </FONT>to detect the presence of a negative-weight cycle.<P>
<a name="08e0_1855">26.1-9<a name="08e0_1855"><P>
Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.<P>
<P>


<P>







<h1><a name="08e1_1850">26.2 The Floyd-Warshall algorithm<a name="08e1_1850"></h1><P>
<a name="08e1_184c"><a name="08e1_184d"><a name="08e1_184e"><a name="08e1_184f">In this section, we shall use a different dynamic-programming formulation to solve the all-pairs shortest-paths problem on a directed graph <I>G</I> = (<I>V, E</I>). The resulting algorithm, known as the <I><B>Floyd-Warshall algorithm</I></B>, runs in <img src="../images/bound.gif">(<I>V</I><SUP>3</SUP>) time. As before, negative-weight edges may be present, but we shall assume that there are no negative-weight cycles. As in Section 26.1, we shall follow the dynamic-programming process to develop the algorithm. After studying the resulting algorithm, we shall present a similar method for finding the transitive closure of a directed graph.<P>





<h2>The structure of a shortest path</h2><P>
<a name="08e2_1850"><a name="08e2_1851"><a name="08e2_1852">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 &quot;intermediate&quot; vertices of a shortest path, where an <I><B>intermediate</I></B> vertex of a simple path <I>p</I> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>, . . . , <I>v</I><SUB>l</SUB><img src="../images/wdrtchv.gif"> is any vertex of <I>p</I> other than <I>v</I><SUB>1</SUB> or <I>v</I><SUB>l</SUB>, that is, any vertex in the set {<I>v</I><SUB>2</SUB>,<I>v</I><SUB>3</SUB>, . . . , <I>v</I><SUB>l-1</SUB>}.<P>
The Floyd-Warshall algorithm is based on the following observation. Let the vertices of <I>G</I> be <I>V</I> = {1, 2, . . . , <I>n</I>}, and consider a subset {1, 2, . . . , <I>k</I>} of vertices for some <I>k</I>. For any pair of vertices <I>i,</I> <I>j</I> <img src="../images/memof12.gif"> <I>V</I>, consider all paths from <I>i</I> to <I>j</I> whose intermediate vertices are all drawn from {1, 2, . . . , <I>k</I>}, and let <I>p</I> be a minimum-weight path from among them. (Path <I>p</I> is simple, since we assume that <I>G</I> contains no negative-weight cycles.) The Floyd- Warshall algorithm exploits a relationship between path <I>p</I> and shortest paths from <I>i</I> to <I>j</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I> - 1}. The relationship depends on whether or not <I>k</I> is an intermediate vertex of path <I>p</I>.<P>
<img src="559_a.gif"><P>
<h4><a name="08e2_1853">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 p<SUB>1</SUB>, 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 p<SUB>2</SUB> from vertex k to vertex j.<a name="08e2_1853"></sub></sup></h4><P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT>     If <I>k</I> is not an intermediate vertex of path <I>p</I>, then all intermediate vertices of path <I>p</I> are in the set {1, 2, . . . , <I>k</I> - 1}. Thus, a shortest path from vertex <I>i</I> to vertex <I>j</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I> - 1} is also a shortest path from <I>i</I> to <I>j</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I>}.<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT>     If <I>k</I> is an intermediate vertex of path <I>p</I>, then we break <I>p</I> down into <img src="559_b.gif"> as shown in Figure 26.3. By Lemma 25.1, <I>p</I><SUB>1</SUB> is a shortest path from <I>i</I> to <I>k</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I>}. In fact, vertex <I>k</I> is not an intermediate vertex of path <I>p</I><SUB>1</SUB>, and so <I>p</I><SUB>1 </SUB>is a shortest path from <I>i</I> to <I>k</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I> - 1}. Similarly, <I>p</I><SUB>2</SUB> is a shortest path from vertex <I>k</I> to vertex <I>j</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I> - 1}.<P>
<P>







<h2>A recursive solution to the all-pairs shortest-paths problem</h2><P>
Based on the above observations, we define a different recursive formulation of shortest-path estimates than we did in Section 26.1. Let <img src="559_c.gif"> be the weight of a shortest path from vertex <I>i</I> to vertex <I>j</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I>}. When <I>k</I> = 0, a path from vertex <I>i</I> to vertex <I>j</I> with no intermediate vertex numbered higher than 0 has no intermediate vertices at all. It thus has at most one edge, and hence <img src="559_d.gif">. A recursive definition is given by<P>
<img src="559_e.gif"><P>
<h4><a name="08e3_0001">(26.5)<a name="08e3_0001"></sub></sup></h4><P>
The matrix <img src="560_a.gif"> gives the final answer--<img src="560_b.gif"> for all <I>i, j</I> <img src="../images/memof12.gif"> <I>V</I>--because all intermediate vertices are in the set {1, 2, . . . , <I>n</I>}.<P>
<P>







<h2>Computing the shortest-path weights bottom up</h2><P>
<a name="08e4_1853">Based on recurrence (26.5), the following bottom-up procedure can be used to compute the values <img src="560_c.gif"> in order of increasing values of <I>k</I>. Its input is an <I>n</I> <img src="../images/mult.gif"> <I>n</I> matrix <I>W</I> defined as in equation (26.1). The procedure returns the matrix <I>D</I><SUP>(<I>n</I>)</SUP> of shortest-path weights.<P>
<img src="560_d.gif"><P>
Figure 26.4 shows a directed graph and the matrices <I>D</I><SUP>(<I>k</I>)</SUP> computed by the Floyd-Warshall algorithm.<P>
The running time of the Floyd-Warshall algorithm is determined by the triply nested <B>for</B> loops of lines 3-6. Each execution of line 6 takes <I>O</I>(1) time. The algorithm thus runs in time <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>). 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 <img src="../images/bound.gif">-notation is small. Thus, the Floyd-Warshall algorithm is quite practical for even moderate-sized input graphs.<P>
<P>







<h2>Constructing a shortest path</h2><P>
There are a variety of different methods for constructing shortest paths in the Floyd-Warshall algorithm. One way is to compute the matrix <I>D</I> of shortest-path weights and then construct the predecessor matrix <img src="../images/piuc.gif"> from the <I>D</I> matrix. This method can be implemented to run in <I>O</I>(<I>n</I><SUP>3</SUP>) time (Exercise 26.1-5). Given the predecessor matrix <img src="../images/piuc.gif">, the <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>ALL</FONT>-<FONT FACE="Courier New" SIZE=2>PAIRS</FONT>-<FONT FACE="Courier New" SIZE=2>SHORTEST</FONT>-<FONT FACE="Courier New" SIZE=2>PATH</FONT> procedure can be used to print the vertices on a given shortest path.<P>
We can compute the predecessor matrix <img src="../images/piuc.gif"> &quot;on-line&quot; just as the Floyd-Warshall algorithm computes the matrices <I>D</I><SUP>(<I>k</I>)</SUP>. Specifically, we compute a sequence of matrices <img src="../images/piuc.gif"><SUP>(0)</SUP>, <img src="../images/piuc.gif"><SUP>(1)</SUP>, . . . , <img src="../images/piuc.gif"><SUP>(<I>n</I>)</SUP>, where <img src="../images/piuc.gif"> = <img src="../images/piuc.gif"><SUP>(<I>n</I>)</SUP> and <img src="560_e.gif"> is defined to be the predecessor of vertex <I>j</I> on a shortest path from vertex <I>i </I>with all intermediate vertices in the set {1, 2, . . . , <I>k</I>}.<P>
We can give a recursive formulation of <img src="560_f.gif">. When <I>k</I> = 0, a shortest path from <I>i</I> to <I>j</I> has no intermediate vertices at all. Thus,<P>
<img src="561_a.gif"><P>
<h4><a name="08e5_0001">Figure 26.4 The sequence of matrices D<SUP>(k)</SUP><FONT FACE="Times New Roman" SIZE=2> and <img src="../images/piuc.gif"><SUP>(k)</SUP><FONT FACE="Times New Roman" SIZE=2> computed by the Floyd-Warshall algorithm for the graph in Figure 26.1.<a name="08e5_0001"></FONT></FONT></sub></sup></h4><P>
<img src="562_a.gif"><P>
<h4><a name="08e5_0002">(26.6)<a name="08e5_0002"></sub></sup></h4><P>
For <I>k</I> <img src="../images/gteq.gif"> 1, if we take the path <img src="562_b.gif">, then the predecessor of <I>j</I> we choose is the same as the predecessor of <I>j</I> we chose on a shortest path from <I>k</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I> - 1}. Otherwise, we choose the same predecessor of <I>j</I> that we chose on a shortest path from <I>i</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I> - 1}. Formally, for <I>k</I> <img src="../images/gteq.gif"> 1,<P>
<img src="562_c.gif"><P>
<h4><a name="08e5_0003">(26.7)<a name="08e5_0003"></sub></sup></h4><P>
We leave the incorporation of the <img src="../images/piuc.gif"><SUP>(<I>k</I>)</SUP> matrix computations into the <FONT FACE="Courier New" SIZE=2>FLOYD</FONT>-<FONT FACE="Courier New" SIZE=2>WARSHALL</FONT> procedure as Exercise 26.2-3. Figure 26.4 shows the sequence of <img src="../images/piuc.gif"><SUP>(<I>k</I>)</SUP> matrices that the resulting algorithm computes for the graph of Figure 26.1. The exercise also asks for the more difficult task of proving that the predecessor subgraph <I>G</I><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB> is a shortest-paths tree with root <I>i</I>. Yet another way to reconstruct shortest paths is given as Exercise 26.2-6.<P>
<P>







<h2>Transitive closure of a directed graph</h2><P>
<a name="08e6_1854"><a name="08e6_1855"><a name="08e6_1856">Given a directed graph <I>G</I> = (<I>V</I>, <I>E</I>) with vertex set <I>V</I> = {1, 2, . . . , <I>n</I>}, we may wish to find out whether there is a path in <I>G</I> from <I>i</I> to <I>j</I> for all vertex pairs <I>i</I>, <I>j</I> <img src="../images/memof12.gif"> <I>V</I>. The <I><B>transitive closure</I></B> of <I>G</I> is defined as the graph <I>G</I>* = (<I>V</I>, <I>E</I>*), where<P>