chap26.htm

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

<I>E</I>* = {(<I>i</I>, <I>j</I>) : there is a path from vertex <I>i</I> to vertex <I>j</I> in <I>G</I>} .<P>
One way to compute the transitive closure of a graph in <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>) time is to assign a weight to 1 to each edge of <I>E</I> and run the Floyd-Warshall algorithm. If there is a path from vertex <I>i</I> to vertex <I>j</I>, we get <I>d<SUB>ij</I></SUB> &lt; <I>n</I>. Otherwise, we get <I>d<SUB>ij</I></SUB> = <FONT FACE="Times New Roman" SIZE=3><img src="../images/infin.gif"></FONT>.<P>
There is another, similar way to compute the transitive closure of <I>G</I> in <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>) time that can save time and space in practice. This method involves substitutions of the logical operations <img src="../images/angledwn.gif"> and <img src="../images/angleup.gif"> for the arithmetic operations min and + in the Floyd-Warshall algorithm. For <I>i</I>, <I>j</I>, <I>k</I> = 1, 2, . . . , <I>n</I>, we define <img src="562_d.gif"> to be 1 if there exists a path in graph <I>G</I> from vertex <I>i</I> to <I>j</I> with all intermediate vertices in the set {1, 2, . . . , <I>k</I>}, and 0 otherwise. We construct the transitive closure <I>G</I>* = (<I>V</I>, <I>E</I>*) by putting edge (<I>i</I>, <I>j</I>) into <I>E</I>* if and only if <img src="562_e.gif"> = 1. A recursive definition of <img src="562_f.gif">, analogous to recurrence (26.5), is<P>
<img src="562_g.gif"><P>
and for <I>k</I> <img src="../images/gteq.gif"> 1,<P>
<img src="563_a.gif"><P>
<h4><a name="08e6_1858">(26.8)<a name="08e6_1858"></sub></sup></h4><P>
As in the Floyd-Warshall algorithm, we compute the matrices <img src="563_b.gif"> in order of increasing <I>k</I>.<P>
<pre><a name="08e6_1857">TRANSITIVE-CLOSURE(<I>G</I>)</sub></sup></pre><P>
<img src="563_c.gif"><P>
Figure 26.5 shows the matrices <I>T</I><SUP>(<I>k</I>)</SUP> computed by the <FONT FACE="Courier New" SIZE=2>TRANSITIVE-</FONT><FONT FACE="Courier New" SIZE=2>CLOSURE</FONT> procedure on a sample graph. Like the Floyd-Warshall algorithm, the running time of the <FONT FACE="Courier New" SIZE=2>TRANSITIVE-</FONT><FONT FACE="Courier New" SIZE=2>CLOSURE</FONT> procedure is <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>). On some computers, though, logical operations on single-bit values execute faster than arithmetic operations on integer words of data. Moreover, because the direct transitive-closure algorithm uses only boolean values rather than integer values, its space requirement is less than the Floyd-Warshall algorithm's by a factor corresponding to the size of a word of computer storage.<P>
In Section 26.4, we shall see that the correspondence between <FONT FACE="Courier New" SIZE=2>FLOYD-</FONT><FONT FACE="Courier New" SIZE=2>WARSHALL</FONT> and <FONT FACE="Courier New" SIZE=2>TRANSITIVE</FONT>-<FONT FACE="Courier New" SIZE=2>CLOSURE</FONT> is more than coincidence. Both algorithms are based on a type of algebraic structure called a "closed semiring."<P>
<P>







<h2><a name="08e7_185b">Exercises<a name="08e7_185b"></h2><P>
<a name="08e7_185c">26.2-1<a name="08e7_185c"><P>
<a name="08e7_1858">Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure 26.2. Show the matrix <I>D</I><SUP>(<I>k</I>)</SUP> that results for each iteration of the outer loop.<P>
<a name="08e7_185d">26.2-2<a name="08e7_185d"><P>
As it appears above, the Floyd-Warshall algorithm requires <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>) space, since we compute <img src="563_d.gif"> for <I>i</I>, <I>j</I>, <I>k</I> = 1, 2, . . . , <I>n</I>. Show that the following procedure, which simply drops all the superscripts, is correct, and thus only <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) space is required.<P>
<img src="564_a.gif"><P>
<h4><a name="08e7_185e">Figure 26.5 A directed graph and the matrices T<SUP>(k)</SUP> computed by the transitive-closure algorithm.<a name="08e7_185e"></sub></sup></h4><P>
<pre><a name="08e7_1859">FLOYD-WARSHALL'(<I>W</I>)</sub></sup></pre><P>
<pre>1  <I>n</I> <img src="../images/arrlt12.gif"> <I>rows</I>[<I>W</I>]</sub></sup></pre><P>
<pre>2  <I>D</I> <img src="../images/arrlt12.gif"> <I>W</I></sub></sup></pre><P>
<pre>3  <B>for</B> <I>k</I> <img src="../images/arrlt12.gif"> 1 <B>to </B><I>n</I></sub></sup></pre><P>
<pre>4       <B>do for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>5              <B>do for</B> <I>j</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>6                 <I>d<SUB>ij</I></SUB> <img src="../images/arrlt12.gif"> min(<I>d<SUB>ij</I></SUB>, <I>d<SUB>ik</I></SUB> + <I>d<SUB>kj</I></SUB>)</sub></sup></pre><P>
<pre>7  <B>return</B> <I>D</I></sub></sup></pre><P>
<a name="08e7_185f">26.2-3<a name="08e7_185f"><P>
Modify the <FONT FACE="Courier New" SIZE=2>FLOYD</FONT>-<FONT FACE="Courier New" SIZE=2>WARSHALL</FONT> procedure to include computation of the <img src="../images/piuc.gif"><SUP>(<I>k</I>)</SUP> matrices according to equations (26.6) and (26.7). Prove rigorously that for all <I>i</I> <img src="../images/memof12.gif"> <I>V</I>, 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>. (<I>Hint</I>: To show that <I>G</I><img src="../images/piuc.gif"><SUB>,<I>i</I></SUB> is acyclic, first show that <img src="564_b.gif"> implies <img src="564_c.gif">. Then, adapt the proof of Lemma 25.8.)<P>
<a name="08e7_1860">26.2-4<a name="08e7_1860"><P>
Suppose that we modify the way in which equality is handled in equation (26.7):<P>
<img src="564_d.gif"><P>
Is this alternative definition of the predecessor matrix <img src="../images/piuc.gif"> correct?<P>
<a name="08e7_1861">26.2-5<a name="08e7_1861"><P>
<a name="08e7_185a">How can the output of the Floyd-Warshall algorithm be used to detect the presence of a negative-weight cycle?<P>
<a name="08e7_1862">26.2-6<a name="08e7_1862"><P>
Another way to reconstruct shortest paths in the Floyd-Warshall algorithm uses values <img src="565_a.gif"> for <I>i</I>, <I>j</I>, <I>k</I> = 1, 2, . . . , <I>n</I>, where <img src="565_b.gif"> is the highest-numbered intermediate vertex of a shortest path from <I>i</I> to <I>j</I>. Give a recursive formulation for <img src="565_c.gif">, modify the <FONT FACE="Courier New" SIZE=2>FLOYD</FONT>-<FONT FACE="Courier New" SIZE=2>WARSHALL</FONT> procedure to compute the <img src="565_d.gif"> values, and rewrite 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 to take the matrix <img src="565_e.gif"> as an input. How is the matrix <img src="../images/phicap12.gif"> like the <I>s</I> table in the matrix-chain multiplication problem of Section 16.1?<P>
<a name="08e7_1863">26.2-7<a name="08e7_1863"><P>
Give an <I>O</I>(<I>V E</I>)-time algorithm for computing the transitive closure of a directed graph <I>G</I> = (<I>V</I>, <I>E</I>).<P>
<a name="08e7_1864">26.2-8<a name="08e7_1864"><P>
Suppose that the transitive closure of a directed acyclic graph can be computed in <img src="../images/scrptf12.gif">(<I>V</I>, <I>E</I>) time, where <img src="../images/scrptf12.gif">(<I>V</I>, <I>E</I>) = <img src="../images/omega12.gif">(<I>V</I> + <I>E</I>) and <img src="../images/scrptf12.gif"> is monotonically increasing. Show that the time to compute the transitive closure of a general directed graph is <I>O</I>(<img src="../images/scrptf12.gif">(<I>V</I>, <I>E</I>)).<P>
<P>


<P>







<h1><a name="08e8_185f">26.3 Johnson's algorithm for sparse graphs<a name="08e8_185f"></h1><P>
<a name="08e8_185b"><a name="08e8_185c"><a name="08e8_185d">Johnson's algorithm finds shortest paths between all pairs in <I>O</I>(<I>V</I><SUP>2</SUP> lg <I>V</I> + <I>V E</I>) time; it is thus asymptotically better than either repeated squaring of matrices or the Floyd-Warshall algorithm for sparse graphs. The algorithm either returns a matrix of shortest-path weights for all pairs or reports that the input graph contains a negative-weight cycle. Johnson's algorithm uses as subroutines both Dijkstra's algorithm and the Bellman-Ford algorithm, which are described in Chapter 25.<P>
<a name="08e8_185e">Johnson's algorithm uses the technique of <I><B>reweighting</I></B>, which works as follows. If all edge weights <I>w</I> in a graph <I>G</I> = (<I>V</I>, <I>E</I>) 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 priority queue, the running time of this all-pairs algorithm is <I>O</I>(<I>V</I><SUP>2 </SUP>lg <I>V</I> + <I>V E</I>). If <I>G </I>has negative-weight edges, we simply compute a new set of nonnegative edge weights that allows us to use the same method. The new set of edge weights <img src="565_f.gif"> must satisfy two important properties.<P>
1.     For all pairs of vertices <I>u</I>, <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, a shortest path from <I>u</I> to <I>v</I> using weight function <I>w</I> is also a shortest path from <I>u</I> to <I>v</I> using weight function <img src="566_a.gif">.<P>
2.     For all edges (<I>u</I>, <I>v</I>), the new weight <img src="566_b.gif"> is nonnegative.<P>
As we shall see in a moment, the preprocessing of <I>G</I> to determine the new weight function <img src="566_c.gif"> can be performed in <I>O</I>(<I>V E</I>) time.<P>





<h2>Preserving shortest paths by reweighting</h2><P>
As the following lemma shows, it is easy to come up with a reweighting of the edges that satisfies the first property above. We use <img src="../images/delta12.gif"> to denote shortest-path weights derived from weight function <I>w</I> and <img src="566_d.gif"> to denote shortest-path weights derived from weight function <img src="566_e.gif">.<P>
<a name="08e9_0001">Lemma 26.1<a name="08e9_0001"><P>
Given a weighted, directed graph <I>G</I> = (<I>V</I>, <I>E</I>) with weight function <I>w</I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B>, let <I>h</I>: <I>V</I> <img src="../images/arrow12.gif"> <B>R</B> be any function mapping vertices to real numbers. For each edge (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I>, define<P>
<img src="566_f.gif"><P>
<h4><a name="08e9_0002">(26.9)<a name="08e9_0002"></sub></sup></h4><P>
Let <I>p</I> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB>, <I>v</I><SUB>l</SUB>, . . . , <I>v<SUB>k</I></SUB>) be a path from vertex <img src="../images/upsil12.gif"><SUB>0</SUB> to vertex <I>v<SUB>k</I></SUB>. Then, <I>w</I>(<I>p</I>) = <img src="../images/delta12.gif">(<I>v</I><SUB>0</SUB>, <I>v<SUB>k</I></SUB>) if and only if <img src="566_g.gif">. Also, <I>G</I> has a negative-weight cycle using weight function <I>w</I> if and only if <I>G</I> has a negative-weight cycle using weight function <img src="566_h.gif">.<P>
<I><B>Proof     </I></B>We start by showing that<P>
<img src="566_i.gif"><P>
<h4><a name="08e9_0003">(26.10)<a name="08e9_0003"></sub></sup></h4><P>
We have<P>
<img src="566_j.gif"><P>
The third equality follows from the telescoping sum on the second line.<P>
We now show by contradiction that <I>w</I>(<I>p</I>) = <img src="../images/delta12.gif">(<I>v</I><SUB>0</SUB>, <I>v<SUB>k</I></SUB>) implies <img src="566_k.gif">. Suppose that there is a shorter path <I>p</I>' from <I>v</I><SUB>0</SUB> to <I>v<SUB>k</I></SUB> using weight function <img src="566_l.gif">. Then, <img src="566_m.gif">. By equation (26.10),<P>
<img src="566_n.gif"><P>
which implies that<I> w</I>(<I>p</I>')<I> </I>&lt;<I> w</I>(<I>p</I>). But this contradicts our assumption that <I>p</I> is a shortest path from <I>u</I> to <I>v</I> using <I>w</I>. The proof of the converse is similar.<P>
Finally, we show that <I>G</I> has a negative-weight cycle using weight function<I> w</I> if and only if <I>G</I> has a negative-weight cycle using weight function <img src="567_a.gif">. Consider any cycle <I>c = </I>&lt;<I>v</I><SUB>0</SUB><I>, v</I><SUB>1</SUB><I>, . . . , v<SUB>k</SUB></I>&gt;, where <I>v</I><SUB>0</SUB><I>= v<SUB>k</I></SUB>. By equation (26.10),<P>
<img src="567_b.gif"><P>
and thus <I>c</I> has negative weight using <I>w</I> if and only if it has negative weight using <img src="567_c.gif">      <P>
<P>