chap25.htm

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

<h2>Shortest-paths trees</h2><P>
<a name="08c7_17e7"><a name="08c7_17e8">So far, we have shown that relaxation causes the shortest-path estimates to descend monotonically toward the actual shortest-path weights. We would also like to show that once a sequence of relaxations has computed the actual shortest-path weights, the predecessor subgraph <I>G</I><img src="../images/piuc.gif"> induced by the resulting <img src="../images/piuc.gif"> values is a shortest-paths ree for <I>G </I>. <U>e </U>start with the following lemma, which shows that the predecessor subgraph always forms a rooted tree whose root is the source.<P>
<a name="08c7_17e9">Lemma 25.8<a name="08c7_17e9"><P>
Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with weight function <I>w </I>: <I>E</I> <img src="../images/arrow12.gif"> <I><B>R</I></B> and source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I>, and assume that <I>G</I> contains no negative-weight cycles that are reachable from <I>s</I>. Then, after the graph is initialized by <FONT FACE="Courier New" SIZE=2>INITIALIZE</FONT>-<FONT FACE="Courier New" SIZE=2>SINGLE</FONT>-<FONT FACE="Courier New" SIZE=2>SOURCE</FONT>(<I>G, s</I>), the predecessor subgraph <I>G</I><img src="../images/piuc.gif"> forms a rooted tree with root <I>s</I>, and any sequence of relaxation steps on edges of <I>G</I> maintains this property as an invariant.<P>
<I><B>Proof     </I></B>Initially, the only vertex in <I>G</I><img src="../images/piuc.gif"> is the source vertex, and the lemma is trivially true. Consider a predecessor subgraph <I>G</I><SUB><img src="../images/piuc.gif"></SUB> that arises after a sequence of relaxation steps. We shall first prove that <I>G</I><img src="../images/piuc.gif"><I></I> is acyclic. Suppose for the sake of contradiction that some relaxation step creates a cycle in the graph <I>G</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/piuc.gif"></FONT>. Let the cycle be <I>c</I> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB>, <I>v</I><SUB>1</SUB>, . . . , <I>v</I><SUB>k</SUB><img src="../images/wdrtchv.gif">, where <I>v</I><SUB><FONT FACE="Courier New" SIZE=2>k</FONT></SUB> = <I>v</I><SUB><FONT FACE="Courier New" SIZE=2>0</FONT></SUB>. Then, <img src="../images/piuc.gif"><I></I>[<I>v<SUB><FONT FACE="Courier New" SIZE=2>i</I></FONT></SUB>] = <I>v<SUB><FONT FACE="Courier New" SIZE=2>i -</I> 1</FONT></SUB> for <I>i</I> = 1, 2, . . ., <I>k</I> and, without loss of generality, we can assume that it was the relaxation of edge (<I>v<SUB><FONT FACE="Courier New" SIZE=2>k - </I>1</FONT></SUB>, <I>v<SUB><FONT FACE="Courier New" SIZE=2>k</I></FONT></SUB>) that created the cycle in <I>G</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/piuc.gif">.</FONT><P>
We claim that all vertices on cycle <I>c</I> are reachable from the source <I>s</I>. Why? Each vertex on <I>c</I> has a non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> predecessor, and so each vertex on <I>c</I> was assigned a finite shortest-path estimate when it was assigned its non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> <img src="../images/piuc.gif"><I></I> value. By Lemma 25.5, each vertex on cycle <I>c</I> has a finite shortest-path weight, which implies that it is reachable from <I>s</I>.<P>
We shall examine the shortest-path estimates on <I>c</I> just prior to the call <FONT FACE="Courier New" SIZE=2>RELAX </FONT>(<I>v<SUB>k - </I>1</SUB>,<I> v<SUB>k</I></SUB>, <I>w</I>) and show that <I>c</I> is a negative-weight cycle, thereby contradicting the assumption that <I>G </I>contains no negative-weight cycles that are reachable from the source. Just before the call, we have <img src="../images/piuc.gif"><I></I>[<I>v<SUB>i</I></SUB>]<I> = v<SUB>i-</I>1</SUB> for <I>i</I> = 1, 2, . . . , <I>k - </I>1. Thus, for <I>i</I> = 1, 2, . . . , <I>k</I> - 1, the last update to <I>d</I>[<I>v<SUB>i</I></SUB>] was by the assignment <I>d</I>[<I>v<SUB>i</I></SUB>] <img src="../images/arrlt12.gif"> <I>d</I>[<I>v<SUB>i -</I> 1</SUB>] + <I>w</I>(<I>v<SUB>i</SUB>,v<SUB>i -</I> 1</SUB>). If <I>d</I>[<I>v<SUB>i - </I>1</SUB>] changed since then, it decreased. Therefore, just before the call <FONT FACE="Courier New" SIZE=2>RELAX</FONT> (<I>v<SUB>k - </I>1</SUB>, <I>v<SUB>k</SUB>, w</I>), we have<P>
<pre><I>d</I>[<I>v<SUB>i</I></SUB>] <img src="../images/gteq.gif"> <I>d</I>[<I>v<SUB>i - </I>1</SUB>]+<I>w</I>(<I>v<SUB>i -</SUB><B><SUB> </I></B>1</SUB>,<I>v<SUB>i</I></SUB>)  for all <I>i</I> = 1, 2,...,<I>k</I> - 1 .</sub></sup></pre><P>
<h4><a name="08c7_17ea">(25.1)<a name="08c7_17ea"></sub></sup></h4><P>
Because <img src="../images/piuc.gif">[<I>v<SUB>k</I></SUB>] is changed by the call, immediately beforehand we also have the strict inequality<P>
<pre><I>d</I>[<I>vk</I>] &gt; <I>d</I>[<I>v<SUB>k</I> - 1</SUB>] + <I>w</I>(<I>v<SUB>k</I> - 1</SUB>, <I>vk</I>) .</sub></sup></pre><P>
Summing this strict inequality with the <I>k</I> - 1 inequalities (25.1), we obtain the sum of the shortest-path estimates around cycle <I>c</I>:<P>
<img src="524_a.gif"><P>
since each vertex in the cycle <I>c</I> appears exactly once in each summation. This implies<P>
<img src="524_b.gif"><P>
Thus, the sum of weights around the cycle <I>c</I> is negative, thereby providing the desired contradiction.<P>
We have now proved that <I>G</I><img src="../images/piuc.gif"><I></I> is a directed, acyclic graph. To show that it forms a rooted tree with root <I>s</I>, it sufiices (see Exercise 5.5-3) to prove that for each vertex <I>v </I><img src="../images/memof12.gif"><I></I> <I>V<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"><I></I>,</FONT> there is a unique path from <I>s</I> to <I>v</I> in <I>G</I><img src="../images/piuc.gif"><I>.</I><P>
We first must show that a path from <I>s</I> exists for each vertex in <I>V</I><img src="../images/piuc.gif">. The vertices in <I>V<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"></FONT> are those with non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> <img src="../images/piuc.gif"><I></I> values, plus <I>s</I>. The idea here is to prove by induction that a path exists from <I>s</I> to all vertices in <I>V</I><img src="../images/piuc.gif">. The details are left as Exercise 25.1-6.<P>
To complete the proof of the lemma, we must now show that for any vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I><img src="../images/piuc.gif"><I>,</I> there is at most one path from <I>s</I> to <I>v</I> in the graph <I>G<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"></FONT>. Suppose otherwise. That is, suppose that there are two simple paths from <I>s</I> to some vertex <I>v:</I> <I>p</I><SUB>1</SUB>, which can be decomposed into <img src="524_c.gif"> and <I>p</I><SUB>2</SUB>, which can be decomposed into <img src="525_d.gif">, where <I>x</I> <img src="../images/noteq.gif"> <I>y</I>. (See Figure 25.4.) But then, <img src="../images/piuc.gif"><I></I>[<I>z</I>] = <I>x</I> and <img src="../images/piuc.gif"><I></I>[<I>z</I>] = <I>y</I>, which implies the contradiction that <I>x</I> = <I>y</I>. We conclude that there exists a unique simple path in  <I>G</I><img src="../images/piuc.gif"> from <I>s</I> to <I>v</I>, and thus <I>G<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"></FONT> forms a rooted tree with root <I>s.     </I> <P>
<img src="525_a.gif"><P>
<h4><a name="08c7_17eb">Figure 25.4  Showing that a path in G<img src="../images/piuc.gif"><SUB></SUB> from source s to vertex v is unique. If there are two paths <img src="525_b.gif"> and <img src="525_c.gif">, where x <img src="../images/noteq.gif"> y, then <img src="../images/piuc.gif">[z] = x and <img src="../images/piuc.gif">[z] = y, a contradiction.<a name="08c7_17eb"></sub></sup></h4><P>
We can now show that if, after we have performed a sequence of relaxation steps, all vertices have been assigned their true shortest-path weights, then the predecessor subgraph <I>G</I><img src="../images/piuc.gif"> is a shortest-paths tree.<P>
<a name="08c7_17ec">Lemma 25.9<a name="08c7_17ec"><P>
Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with weight function <I>w </I>: E <img src="../images/arrow12.gif"> <B>R</B> and source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I>, and assume that <I>G</I> contains no negative-weight cycles that are reachable from <I>s</I>. Let us call <FONT FACE="Courier New" SIZE=2>INITIALIZE</FONT>-<FONT FACE="Courier New" SIZE=2>SINGLE</FONT>-<FONT FACE="Courier New" SIZE=2>SOURCE</FONT>(<I>G, s</I>) and then execute any sequence of relaxation steps on edges of <I>G</I> that produces <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, v</I>) for all <I>v </I><img src="../images/memof12.gif"> <I>V</I>. Then, the predecessor subgraph <I>G</I><img src="../images/piuc.gif"> is a shortest-paths tree rooted at <I>s</I>.<P>
<I><B>Proof     </I></B>We must prove that the three properties of shortest-paths trees hold for <I>G</I><img src="../images/piuc.gif"><I>. </I>To show the first property, we must show that <I>V<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"> </FONT>is the set of vertices reachable from <I>s</I>. By definition, a shortest-path weight <img src="../images/delta12.gif">(<I>s, v</I>) is finite if and only if <I>v</I> is reachable from <I>s</I>, and thus the vertices that are reachable from <I>s</I> are exactly those with finite <I>d</I> values. But a vertex <I>v </I><img src="../images/memof12.gif"> <I>V</I> - {<I>s</I>} has been assigned a finite value for <I>d</I>[<I>v</I>] if and only if <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/noteq.gif"> <FONT FACE="Courier New" SIZE=2>NIL</FONT>. Thus, the vertices in <I>V</I><img src="../images/piuc.gif"><SUP> </SUP>are exactly those reachable from <I>s</I>.<P>
The second property follows directly from Lemma 25.8.<P>
It remains, therefore, to prove the last property of shortest-paths trees: for all <I>v </I><img src="../images/memof12.gif"> <I>V</I><img src="../images/piuc.gif">, the unique simple path <img src="525_e.gif"> in <I>G<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"></FONT> is a shortest path from <I>s</I> to <I>v </I>in <I>G</I>. Let <I>p</I> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB><I>, v</I><SUB>1</SUB>, . . . , <I>v<SUB>k</I></SUB><img src="../images/wdrtchv.gif">, where <I>v</I><SUB>0</SUB> = <I>s</I> and <I>v<SUB>k</I></SUB> = <I>v</I>. For <I>i</I> = l, 2, . . . , <I>k</I>, we have both <I>d</I>[<I>v<SUB>i</I></SUB>]<I> = </I><img src="../images/delta12.gif"><I>(s</I>, <I>v<SUB>i</I></SUB>) and <I>d</I>[<I>v<SUB>i</I></SUB>] <img src="../images/gteq.gif"><I> d</I>[<I>v<SUB>i - </I>1</SUB>] + <I>w</I>(<I>v<SUB>i - </I>1</SUB>, <I>v<SUB>i</I></SUB>),<I><SUB> </I></SUB>from which we conclude <I>w</I>(<I>v<SUB>i-</I>1</SUB>, <I>v<SUB>i</I></SUB>) <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"><I></I>(<I>s, v<SUB>i</I></SUB>) - <img src="../images/delta12.gif"><I></I>(<I>s, v<SUB>i - </I>1</SUB>). Summing the weights along path <I>p</I> yields<P>
<img src="525_f.gif"><P>
<img src="526_a.gif"><P>
<pre>=  <img src="../images/delta12.gif">(s, v<SUB>k</SUB>) - <img src="../images/delta12.gif">(s, v<SUB>0)</sub></sup></pre><P>
<pre>=  <SUB><img src="../images/delta12.gif"></SUB>(<SUB>s, v</SUB>k<SUB>).</sub></sup></pre><P>
The third line comes from the telescoping sum on the second line, and the fourth line follows from <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I><SUB>0</SUB>) =    <img src="../images/delta12.gif"><I></I>(<I>s, s</I>) = 0. Thus, <I>w(p)</I> <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"><I></I>(s, <I>v</I><SUB>k</SUB>). Since <img src="../images/delta12.gif"><I></I>(s, <I>v</I><SUB>k</SUB>) is a lower bound on the weight of any path from s to <I>v<SUB>k</I></SUB>, we conclude that <I>w</I>(<I>p</I>) = <img src="../images/delta12.gif"><I></I>(<I>s, v<SUB>k</I></SUB>), and thus <I>p</I> is a shortest path from <I>s</I> to <I>v</I> = <I>v<SUB>k</I></SUB>.      <P>
<P>







<h2><a name="08c8_17ea">Exercises<a name="08c8_17ea"></h2><P>
<a name="08c8_17eb">25.1-1<a name="08c8_17eb"><P>
Give two shortest-paths trees for the directed graph of Figure 25.2 other than the two shown.<P>
<a name="08c8_17ec">25.1-2<a name="08c8_17ec"><P>
Give an example of a weighted, directed graph <I>G</I> = (<I>V, E</I>) with weight function <I>w:</I> E <img src="../images/arrow12.gif"> <B>R</B> and source <I>s</I> such that <I>G</I> satisfies the following property: For every edge (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E,</I> there is a shortest-paths tree rooted at<I> s</I> that contains (<I>u, v</I>) and another shortest-paths tree rooted at <I>s</I> that does not contain (<I>u, v</I>).<P>
<a name="08c8_17ed">25.1-3<a name="08c8_17ed"><P>
Embellish the proof of Lemma 25.3 to handle cases in which shortest-path weights are <img src="../images/infin.gif"> or -<img src="../images/infin.gif">.<P>
<a name="08c8_17ee">25.1-4<a name="08c8_17ee"><P>
Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with source vertex <I>s</I>, and let <I>G</I> be initialized by <FONT FACE="Courier New" SIZE=2>INITIALIZE</FONT>-<FONT FACE="Courier New" SIZE=2>SINGLE</FONT>-<FONT FACE="Courier New" SIZE=2>SOURCE</FONT>(<I>G, s</I>). Prove that if a sequence of relaxation steps sets <img src="../images/piuc.gif">[<I>s</I>] to a non-<FONT FACE="Courier New" SIZE=2>NIL</FONT> value, then <I>G</I> contains a negative-weight cycle.<P>
<a name="08c8_17ef">25.1-5<a name="08c8_17ef"><P>
<a name="08c8_17e9">Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with no negative-weight edges. Let <I>s</I> <img src="../images/memof12.gif"> <I>V</I> be the source vertex, and let us define <img src="../images/piuc.gif">[<I>v</I>] as usual: <img src="../images/piuc.gif"><I></I>[<I>v</I>] is the predecessor of <I>v</I> on some shortest path to <I>v</I> from source <I>s</I> if <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s</I>} is reachable from <I>s</I>, and <FONT FACE="Courier New" SIZE=2>NIL</FONT> otherwise. Give an example of such a graph <I>G</I> and an assignment of <img src="../images/piuc.gif"> values that produces a cycle in <I>G</I><img src="../images/piuc.gif"><I>.</I> (By Lemma 25.8, such an assignment cannot be produced by a sequence of relaxation steps.)<P>
<a name="08c8_17f0">25.1-6<a name="08c8_17f0"><P>
Let <I>G</I> = (<I>V, E</I>) be a weighted, directed graph with weight function <I>w </I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B> and no negative-weight cycles. Let <I>s</I> <img src="../images/memof12.gif"> <I>V</I> be the source vertex, and let <I>G</I> be initialized by <FONT FACE="Courier New" SIZE=2>INITIALIZE</FONT>-<FONT FACE="Courier New" SIZE=2>SINGLE</FONT>-<FONT FACE="Courier New" SIZE=2>SOURCE</FONT>(<I>G, s</I>). Prove that for every vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I><img src="../images/piuc.gif"><I></I>, there exists a path from <I>s</I> to <I>v</I> in <I>G<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/piuc.gif"><I><SUB></I></FONT></SUB> and that this property is maintained as an invariant over any sequence of relaxations.<P>
<a name="08c8_17f1">25.1-7<a name="08c8_17f1"><P>