chap25.htm

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

<h2>Relaxation</h2><P>
<a name="08c5_17e2"><a name="08c5_17e3"><a name="08c5_17e4">The algorithms in this chapter use the technique of <I><B>relaxation</I></B>. For each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, we maintain an attribute <I>d</I>[<I>v</I>], which is an upper bound on the weight of a shortest path from source <I>s</I> to <I>v</I>. We call <I>d</I>[<I>v</I>] a <I><B>shortest-path</I></B> <I><B>estimate</I></B>. We initialize the shortest-path estimates and predecessors by the following procedure.<P>
<pre><a name="08c5_17e5">INITIALIZE-SINGLE-SOURCE(<I>G,s</I>)</sub></sup></pre><P>
<pre>1<B>  for</B> each vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I>[<I>G</I>]</sub></sup></pre><P>
<pre>2<B>       do</B> <I>d</I>[<I>v</I>] <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>3          <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
<pre>4<I>  d</I>[<I>s</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
After initialization, <img src="../images/piuc.gif">[<I>v</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT> for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, <I>d</I>[<I>v</I>] = 0 for <I>v</I> = <I>s</I>, and <I>d</I>[<I>v</I>] = <img src="../images/infin.gif"> for <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s</I>}.<P>
The process of <I><B>relaxing</I></B><SUP>1</SUP> an edge (<I>u</I>, <I>v</I>) consists of testing whether we can improve the shortest path to <I>v</I> found so far by going through <I>u</I> and, if so, updating <I>d</I>[<I>v</I>] and <img src="../images/piuc.gif">[<I>v</I>]. A relaxation step may decrease the value of the shortest-path estimate <I>d</I>[<I>v</I>] and update <I>v'</I>s predecessor field <img src="../images/piuc.gif">[<I>v</I>]. The following code performs a relaxation step on edge (<I>u</I>, <I>v</I>).<P>
<SUP>1</SUP>It may seem strange that the term &quot;relaxation&quot; is used for an operation that tightens an upper bound. The use of the term is historical. The outcome of a relaxation step can be viewed as a relaxation of the constraint <I>d</I>[<I>v</I>] <img src="../images/lteq12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>), which, by Lemma 25.3, must be satisfied if <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I>(</I>s<I>, </I>u<I>) and </I>d<I>[</I>v<I>] = <img src="../images/delta12.gif"></I>(<I>s</I>, <I>v</I>). That is, if <I>d</I>[<I>v</I>] <img src="../images/lteq12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>), there is no "pressure" to satisfy this constraint, so the constraint is &quot;relaxed.&quot;<P>
<pre><a name="08c5_17e6">RELAX(<I>u</I>, <I>v</I>, <I>w</I>)</sub></sup></pre><P>
<pre>1<B> if</B> <I>d</I>[<I>v</I>] &gt; <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>,<I>v</I>)</sub></sup></pre><P>
<pre>2<B>    then</B> <I>d</I>[<I>v</I>] <img src="../images/arrlt12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>,<I>v</I>)</sub></sup></pre><P>
<pre>3         <img src="../images/piuc.gif">[<I>v</I>] <img src="../images/arrlt12.gif"> <I>u</I></sub></sup></pre><P>
Figure 25.3 shows two examples of relaxing an edge, one in which a shortest-path estimate decreases and one in which no estimate changes.<P>
<img src="521_a.gif"><P>
<h4><a name="08c5_17e7">Figure 25.3 Relaxation of an edge (u, v). The shortest-path estimate of each vertex is shown within the vertex. (a) Because d[v] &gt; d[u] + w(u, v) prior to relaxation, the value of d[v] decreases. (b) Here, d[v] <img src="../images/lteq12.gif"> d[u] + w(u, v) before the relaxation step, so d[v] is unchanged by relaxation.<a name="08c5_17e7"></sub></sup></h4><P>
Each algorithm in this chapter calls <FONT FACE="Courier New" SIZE=2>INITIALIZE</FONT>-<FONT FACE="Courier New" SIZE=2>SINGLE</FONT>-S<FONT FACE="Times New Roman" SIZE=1>OURCE</FONT> and then repeatedly relaxes edges. Moreover, relaxation is the only means by which shortest-path estimates and predecessors change. The algorithms in this chapter differ in how many times they relax each edge and the order in which they relax edges. In Dijkstra's algorithm and the shortest-paths algorithm for directed acyclic graphs, each edge is relaxed exactly once. In the Bellman-Ford algorithm, each edge is relaxed several times.<P>
<P>







<h2>Properties of relaxation</h2><P>
The correctness of the algorithms in this chapter depends on important properties of relaxation that are summarized in the next few lemmas. Most of the lemmas describe the outcome of executing a sequence of relaxation steps on the edges of a weighted, directed graph that has been 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>. Except for Lemma 25.9, these lemmas apply to <I>any</I> sequence of relaxation steps, not just those that produce shortest-path values.<P>
<a name="08c6_0001">Lemma 25.4<a name="08c6_0001"><P>
Let <I>G</I> = (<I>V</I>, <I>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 let (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I>. Then, immediately after relaxing edge (<I>u</I>, <I>v</I>) by executing <FONT FACE="Courier New" SIZE=2>RELAX</FONT>(<I>u</I>, <I>v</I>, <I>w</I>), we have <I>d</I>[<I>v</I>] <img src="../images/lteq12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>).<P>
<I><B>Proof     </I></B>If, just prior to relaxing edge (<I>u</I>, <I>v</I>), we have <I>d</I>[<I>v</I>] &gt; <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>), then <I>d</I>[<I>v</I>] = <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>) afterward. If, instead, <I>d</I>[<I>v</I>] <img src="../images/lteq12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>) just before the relaxation, the neither <I>d</I>[<I>u</I>] nor <I>d</I>[<I>v</I>] changes, and so <I>d</I>[<I>v</I>] <img src="../images/lteq12.gif"> <I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>) afterward.      <P>
<a name="08c6_0002">Lemma 25.5<a name="08c6_0002"><P>
Let <I>G</I> = (<I>V</I>, <I>E</I>) be a weighted, directed graph with weight function <I>w</I> : <I>E</I> <img src="../images/arrow12.gif"> <B>R</B>. Let <I>s</I> <img src="../images/memof12.gif"> <I>V</I> be the source vertex, and let the graph 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</I>, <I>s</I>). Then, <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, and this invariant is maintained over any sequence of relaxation steps on the edges of <I>G</I>. Moreover, once <I>d</I>[<I>v</I>] achieves its lower bound <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>), it never changes.<P>
<I><B>Proof     </I></B>The invariant <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) is certainly true after initialization, since <I>d</I>[<I>s</I>] = 0 <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>s</I>) (note that <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>s</I>) is - <img src="../images/infin.gif"> if <I>s</I> is on a negative-weight cycle and 0 otherwise) and <I>d</I>[<I>v</I>] = <img src="../images/infin.gif"> implies <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s</I>}. We shall use proof by contradiction to show that the invariant is maintained over any sequence of relaxation steps. Let <I>v</I> be the first vertex for which a relaxation step of an edge (<I>u</I>, <I>v</I>) causes <I>d</I>[<I>v</I>] &lt; <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>). Then, just after relaxing edge (<I>u</I>, <I>v</I>), we have<P>
<pre><I>d</I>[<I>u</I>] + <I>w</I>(<I>u</I>, <I>v</I>)  =  <I>d</I>[<I>v</I>]</sub></sup></pre><P>
<pre>&lt;  <img src="../images/delta12.gif">(s,v)</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">  <img src="../images/delta12.gif">(s,u) + w(u, v)  (by Lemma 25.3),</sub></sup></pre><P>
which implies that <I>d</I>[<I>u</I>] &lt; <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>u</I>). But because relaxing edge (<I>u</I>, <I>v</I>) does not change <I>d</I>[<I>u</I>], this inequality must have been true just before we relaxed the edge, which contradicts the choice of <I>v</I> as the first vertex for which <I>d</I>[<I>v</I>] &lt; <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>). We conclude that the invariant <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>) is maintained for all <I>v</I> <img src="../images/memof12.gif"> <I>V</I>.<P>
To see that the value of <I>d</I>[<I>v</I>] never changes once <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>), note that having achieved its lower bound, <I>d</I>[<I>v</I>] cannot decrease because we have just shown that <I>d</I>[<I>v</I>] <img src="../images/gteq.gif"> <img src="../images/delta12.gif"><I></I>(<I>s</I>, <I>v</I>), and it cannot increase because relaxation steps do not increase <I>d</I> values.      <P>
<a name="08c6_0003">Corollary 25.6<a name="08c6_0003"><P>
Suppose that in 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>, no path connects a source vertex <I>s</I> <img src="../images/memof12.gif"> <I>V</I> to a given vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</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>), we have <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, v</I>), and this equality is maintained as an invariant over any sequence of relaxation steps on the edges of <I>G</I>.<P>
<I><B>Proof     </I></B>By Lemma 25.5, we always have <img src="../images/infin.gif"> = <img src="../images/delta12.gif"><I>(</I>s, v<I>) <img src="../images/lteq12.gif"> </I>d<I>[</I>v<I>]; thus, so </I>d<I>[</I>v<I>] = <img src="../images/infin.gif"> = <img src="../images/delta12.gif"></I>(<I>s, v</I>).      <P>
The following lemma is crucial to proving the correctness of the shortest-paths algorithms that appear later in this chapter. It gives sufficient conditions for relaxation to cause a shortest-path estimate to converge to a shortest-parth weight.<P>
<a name="08c6_0004">Lemma 25.7<a name="08c6_0004"><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>, let <I>s</I> <img src="../images/memof12.gif"> <I>V</I> be a source vertex, and let <img src="522_a.gif"> be a shortest path in <I>G</I> for some vertices <I>u, v </I><img src="../images/memof12.gif"><I> V</I>. Suppose that <I>G</I> 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>) and then a sequence of relaxation steps that includes the call <FONT FACE="Courier New" SIZE=2>RELAX</FONT>(<I>u, v, w</I>) is executed on the edges of <I>G</I>. If <I>d</I>[<I>u</I>] =<img src="../images/delta12.gif"><I></I>(<I>s, u</I>) at any time prior to the call, then <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, v</I>) at all times after the call.<P>
<I><B>Proof     </I></B>By Lemma 25.5, if <I>d</I>[<I>u</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, u</I>) at some point prior to relaxing edge (<I>u, v</I>), then this equality holds thereafter. In particular, after relaxing edge (<I>u</I>, <I>v)</I> we have<P>
<pre><I>d</I>[<I>v</I>]  <img src="../images/lteq12.gif">  <I>d</I>[<I>u</I>] + <I>w</I>(<I>u,v</I>)    (by Lemma 25.4)</sub></sup></pre><P>
<pre>=  <img src="../images/delta12.gif">(s,u) + w(u,v)</sub></sup></pre><P>
<pre>=  <img src="../images/delta12.gif">(s,v)           (by Corollary 25.2).</sub></sup></pre><P>
By Lemma 25.5, <img src="../images/delta12.gif"><I></I>(<I>s, v</I>) bounds <I>d</I>[<I>v</I>] from below, from which we conclude that <I>d</I>[<I>v</I>] = <img src="../images/delta12.gif"><I></I>(<I>s, v</I>), and this equality is maintained thereafter.      <P>
<P>