chap27.htm

CLRS-算法导论

<h2>The basic Ford-Fulkerson algorithm</h2><P>
In each iteration of the Ford-Fulkerson method, we find <I>any</I> augmenting path <I>p</I> and augment flow &acirc; along <I>p</I> by the residual capacity c<SUB>&acirc;</SUB>(<I>p</I>). The following implementation of the method computes the maximum flow in a graph <I>G</I> = (<I>V</I>, <I>E</I>) by updating the net flow &acirc;[<I>u</I>, <I>v</I>] between each pair <I>u</I>, <I>v</I> of vertices that are connected by an edge.<SUP>1</SUP> If <I>u</I> and <I>v</I> are not connected by an edge in either direction, we assume implicitly that &acirc;[<I>u</I>, <I>v</I>] = 0. The code assumes that the capacity from <I>u</I> to <I>v</I> is provided by a constant-time function <I>c</I>(<I>u</I>, <I>v</I>), with <I>c</I>(<I>u</I>, <I>v</I>) = 0 if (<I>u</I>, <I>v</I>) <img src="../images/notmem.gif"> <I>E</I>. (In a typical implementation, <I>c</I>(<I>u</I>, <I>v</I>) might be derived from fields stored within vertices and their adjacency lists.) The residual capacity <I>c</I><SUB>&acirc;</SUB>(<I>u</I>, <I>v</I>) is computed in accordance with the formula (27.5). The expression c<SUB>&acirc;</SUB>(<I>p</I>) in the code is actually just a temporary variable that stores the residual capacity of the path <I>p</I>.<P>
<SUP>1</SUP>We use square brackets when we treat an identifier--such as &acirc;--as a mutable field, and we use parentheses when we treat it as a function.<P>
<pre><a name="0901_18c0">FORD-FULKERSON(<I>G</I>, <I>s</I>, <I>t</I>)</sub></sup></pre><P>
<pre>1  <B>for</B> each edge (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I>[<I>G</I>]</sub></sup></pre><P>
<pre>2       <B>do</B> <I>&acirc;</I>[<I>u</I>, <I>v</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>3          <I>&acirc;</I>[<I>v</I>, <I>u</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>4  <B>while</B> there exists a path <I>p</I> from <I>s</I> to <I>t</I> in the residual network <I>G</I><SUB>&acirc;</sub></sup></pre><P>
<pre>5      <B>do</B> <I>c</I><SUB>&acirc;</SUB>(<I>p</I>) <img src="../images/arrlt12.gif"> min {<I>c</I><SUB>&acirc;</SUB>(<I>u</I>, <I>v</I>) : (<I>u</I>, <I>v</I>) is in <I>p</I>}</sub></sup></pre><P>
<pre>6         <B>for</B> each edge (<I>u</I>, <I>v</I>) in <I>p</I></sub></sup></pre><P>
<pre>7             <B>do</B> <I>&acirc;</I>[<I>u</I>, <I>v</I>] <img src="../images/arrlt12.gif"> <I>&acirc;</I>[<I>u</I>, <I>v</I>]+<I>c</I><SUB>&acirc;</SUB>(<I>p</I>)</sub></sup></pre><P>
<pre>8                <I>&acirc;</I>[<I>v</I>, <I>u</I>] <img src="../images/arrlt12.gif"> - <I>&acirc;</I>[<I>u</I>, <I>v</I>]</sub></sup></pre><P>
The <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKERSON</FONT> algorithm simply expands on the <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKER</FONT>-<FONT FACE="Courier New" SIZE=2>SON</FONT>-<FONT FACE="Courier New" SIZE=2>METHOD</FONT> pseudocode given earlier. Figure 27.6 shows the result of each iteration in a sample run. Lines 1-3 initialize the flow &acirc; to 0. The <B>while</B> loop of lines 4-8 repeatedly finds an augmenting path <I>p</I> in <I>G</I><SUB>&acirc;</SUB> and augments flow &acirc; along <I>p</I> by the residual capacity <I>c</I><SUB>&acirc;</SUB>(<I>p</I>). When no augmenting paths exist, the flow &acirc; is a maximum flow.<P>
<P>







<h2>Analysis of Ford-Fulkerson</h2><P>
The running time of <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKERSON</FONT> depends on how the augmenting path <I>p</I> in line 4 is determined. If it is chosen poorly, the algorithm might not even terminate: the value of the flow will increase with successive augmentations, but it need not even converge to the maximum flow value. If the augmenting path is chosen by using a breadth-first search (Section 23.2), however, the algorithm runs in polynomial time. Before proving this, however, we obtain a simple bound for the case in which the augmenting path is chosen arbitrarily and all capacities are integers.<P>
Most often in practice, the maximum-flow problem arises with integral capacities. If the capacities are rational numbers, an appropriate scaling transformation can be used to make them all integral. Under this assumption, a straightforward implementation of <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKERSON</FONT> runs in time <I>O</I>(<I>E</I> | &acirc;* |), where &acirc;* is the maximum flow found by the algorithm. The analysis is as follows. Lines 1-3 take time <img src="../images/bound.gif"><B>(<I>E</I>)</B>. The <B>while</B> loop of lines 4-8 is executed at most | &acirc;* | times, since the flow value increases by at least one unit in each iteration.<P>
The work done within the <B>while</B> loop can be made efficient if we efficiently manage the data structure used to implement the network <I>G</I> = (<I>V</I>, <I>E</I>). Let us assume that we keep a data structure corresponding to a directed graph <I>G</I>' = (<I>V</I>, <I>E</I>'), where <I>E</I>' = {(<I>u</I>, <I>v</I>) : (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I> or (<I>v</I>, <I>u</I>) <img src="../images/memof12.gif"> <I>E</I>}. Edges in the network <I>G</I> are also edges in <I>G</I>', and it is therefore a simple matter to maintain capacities and flows in this data structure. Given a flow &acirc; on <I>G</I>, the edges in the residual network <I>G</I><SUB>&acirc;</SUB> consist of all edges (<I>u</I>, <I>v</I>) of <I>G</I>' such that <I>c</I>(<I>u</I>, <I>v</I>) - &acirc;[<I>u</I>, <I>v</I>] <img src="../images/noteq.gif"> 0. The time to find a path in a residual network is therefore <I>O</I>(<I>E</I>') = <I>O</I>(<I>E</I>) if we use either depth-first search or breadth-first search. Each iteration of the <B>while</B> loop thus takes <I>O</I>(<I>E</I>) time, making the total running time of <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKERSON</FONT> <I>O</I>(<I>E</I> | &acirc;* |).<P>
<img src="595_a.gif"><P>
<h4><a name="0902_18c4">Figure 27.6 The execution of the basic Ford-Fulkerson algorithm. (a)-(d) Successive iterations of the while loop. The left side of each part shows the residual network G<SUB>&acirc;</SUB> from line 4 with a shaded augmenting path p. The right side of each part shows the new flow &acirc; that results from adding &acirc;<SUB>p</SUB> to &acirc;. The residual network in (a) is the input network G. (e) The residual network at the last while loop test. It has no augmenting paths, and the flow &acirc; shown in (d) is therefore a maximum flow.<a name="0902_18c4"></sub></sup></h4><P>
<img src="596_a.gif"><P>
<h4><a name="0902_18c5">Figure 27.7 (a) A flow network for which <FONT FACE="Courier New" SIZE=2>FORD-FULKERSON</FONT> can take <img src="../images/bound.gif">(E |&acirc;*|) time, where &acirc;* is a maximum flow, shown here with | &acirc;* | = 2,000,000. An augmenting path with residual capacity 1 is shown. (b) The resulting residual network. Another augmenting path with residual capacity 1 is shown. (c) The resulting residual network.<a name="0902_18c5"></sub></sup></h4><P>
When the capacities are integral and the optimal flow value | &acirc;* | is small, the running time of the Ford-Fulkerson algorithm is good. Figure 27.7(a) shows an example of what can happen on a simple flow network for which | &acirc;* | is large. A maximum flow in this network has value 2,000,000: 1,000,000 units of flow traverse the path <I>s</I> <img src="../images/arrow12.gif"> <I>u</I> <img src="../images/arrow12.gif"> <I>t</I>, and another 1,000,000 units traverse the path <I>s</I> <img src="../images/arrow12.gif"> <I>v</I> <img src="../images/arrow12.gif"> <I>t</I>. If the first augmenting path found by <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKERSON</FONT> is <I>s</I> <img src="../images/arrow12.gif"> <I>u</I> <img src="../images/arrow12.gif"> <I>v </I><img src="../images/arrow12.gif"> <I>t</I>, shown in Figure 27.7(a), the flow has value 1 after the first iteration. The resulting residual network is shown in Figure 27.7(b). If the second iteration finds the augmenting path <I>s</I> <img src="../images/arrow12.gif"> <I>v</I> <img src="../images/arrow12.gif"> <I>u</I> <img src="../images/arrow12.gif"> <I>t</I>, as shown in Figure 27.7(b), the flow then has value 2. Figure 27.7(c) shows the resulting residual network. We can continue, choosing the augmenting path <I>s</I> <img src="../images/arrow12.gif"> <I>u</I> <img src="../images/arrow12.gif"> <I>v</I> <img src="../images/arrow12.gif"> <I>t</I> in the odd-numbered iterations and the augmenting path <I>s</I> <img src="../images/arrow12.gif"> <I>v</I> <img src="../images/arrow12.gif"> <I>u</I> <img src="../images/arrow12.gif"> <I>t</I> in the even-numbered iterations. We would perform a total of 2,000,000 augmentations, increasing the flow value by only 1 unit in each.<P>
<a name="0902_18c1">The bound on <FONT FACE="Courier New" SIZE=2>FORD</FONT>-<FONT FACE="Courier New" SIZE=2>FULKERSON</FONT> can be improved if we implement the computation of the augmenting path <I>p</I> in line 4 with a breadth-first search, that is, if the augmenting path is a <I>shortest</I> path from <I>s</I> to <I>t</I> in the residual network, where each edge has unit distance (weight). We call the Ford-Fulkerson method so implemented the <I><B>Edmonds-Karp algorithm.</I></B> We now prove that the Edmonds-Karp algorithm runs in <I>O</I>(<I>V E</I><SUP>2</SUP>) time.<P>
The analysis depends on the distances to vertices in the residual network G<I><SUB>f</I></SUB>. The following lemma uses the notation <img src="../images/delta12.gif"><I></I><img src="../images/scrptf12.gif">(<I>u</I>, <I>v</I>) for the shortest-path distance from <I>u</I> to <I>v</I> in <I>G<SUB><FONT FACE="Courier New" SIZE=2>f</I></FONT></SUB> , where each edge has unit distance.<P>
<a name="0902_18c6">Lemma 27.8<a name="0902_18c6"><P>
If the Edmonds-Karp algorithm is run on a flow network <I>G</I> = (<I>V, E</I>) with source <I>s</I> and sink <I>t</I>, then for all vertices <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s, t</I>}, the shortest-path distance <img src="../images/delta12.gif"><I></I><img src="../images/scrptf12.gif">(<I>s</I>, <I>v</I>) in the residual network <I>G<SUB><FONT FACE="Courier New" SIZE=2>f</I></FONT></SUB> increases monotonically with each flow augmentation.<P>
<I><B>Proof     </I></B>Suppose for the purpose of contradiction that for some vertex <I>v</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s, t</I>}, there is a flow augmentation that causes <img src="../images/delta12.gif"><I></I><img src="../images/scrptf12.gif">(<I>s, v</I>) to decrease. Let <I>f</I> be the flow just before the augmentation, and let <img src="../images/scrptf12.gif">' be the flow just afterward. Then,<P>
<pre><img src="../images/delta12.gif"><SUB></SUB><img src="../images/scrptf12.gif">'<SUB>(<I>s</I>, <I>v</I>) &lt; <img src="../images/delta12.gif"></SUB><SUB><img src="../images/scrptf12.gif"></SUB>(<I>s</I>, <I>v</I>).</sub></sup></pre><P>
We can assume without loss of generality that <img src="../images/delta12.gif"><I></I><img src="../images/scrptf12.gif">'(<I>s</I>, <I>v</I>) <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"><I></I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/scrptf12.gif">'</FONT>(<I>s, u</I>) for all vertices <I>u</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s, t</I>} such that <img src="../images/delta12.gif"><I></I><img src="../images/scrptf12.gif">'(<I>s, u</I>) &lt; <img src="../images/delta12.gif"><I></I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/scrptf12.gif"></FONT>(<I>s, u</I>). Equivalently, we can assume that for all vertices <I>u</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s, t</I>},<P>
<pre><img src="../images/delta12.gif"><I></I><SUB></SUB><img src="../images/scrptf12.gif">'<SUB>(<I>s, u</I>) &lt; <img src="../images/delta12.gif"><I></SUB><SUB><img src="../images/scrptf12.gif">'</SUB>(</I>s<I>, </I>v<I>) implies <img src="../images/delta12.gif"></I><SUB></SUB><img src="../images/scrptf12.gif"><SUB>(<I>s, u</I>) <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"><I></SUB><SUB><img src="../images/scrptf12.gif">'</SUB>(</I>s, u<I>).</I></sub></sup></pre><P>
<h4><a name="0902_18c7">(27.7)<a name="0902_18c7"></sub></sup></h4><P>
We now take a shortest path p' in G<img src="../images/scrptf12.gif">' of the form <img src="597_a.gif"> and consider the vertex <I>u</I> that precedes <I>v</I> on this path. We must have <img src="../images/delta12.gif"><I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/scrptf12.gif"></I>'</FONT><I><SUB>(</I>s, u<I>) = <img src="../images/delta12.gif"></I><img src="../images/scrptf12.gif"><I>'</I></SUB>(<I>s</I>, <I>v</I>) - 1 by Corollary 25.2, since (<I>u</I>, <I>v</I>) is an edge on p', which is a shortest path from <I>s</I> to <I>v</I>. By our assumption (27.7), therefore,<P>
<pre><img src="../images/delta12.gif"><I><SUB></SUB><img src="../images/scrptf12.gif"><SUB>(</I>s, u<I>) <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"></I></SUB><SUB><img src="../images/scrptf12.gif"><I>'</I></SUB>(<I>s, u</I>) .</sub></sup></pre><P>
With vertices <I>v</I> and <I>u</I> thus established, we can consider the net flow &acirc;<I> </I>from <I>u</I> to <I>v</I> before the augmentation of flow in <I>G</I><img src="../images/scrptf12.gif">. If &acirc;[<I>u</I>, <I>v</I>] &lt; <I>c</I>(<I>u</I>, <I>v</I>), then we have<P>
<pre><img src="../images/delta12.gif"><I><SUB></SUB><img src="../images/scrptf12.gif"><SUB>(</I>s<I>, </I>v<I>)  <img src="../images/lteq12.gif">  <img src="../images/delta12.gif"></I></SUB><SUB><img src="../images/scrptf12.gif"></SUB>(<I>s, u</I>) + 1    (by Lemma 25.3)</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">   <img src="../images/delta12.gif"><I><SUB></SUB><img src="../images/scrptf12.gif"></I>'<I><SUB>(</I>s<I>, </I>u<I>) + 1</I></sub></sup></pre><P>
<pre>=   <img src="../images/delta12.gif"><I><SUB></SUB><img src="../images/scrptf12.gif"></I>'<I><SUB>(</I>s<I>, </I>v<I>) ,</I></sub></sup></pre><P>
which contradicts our assumption that the flow augmentation decreases the distance from <I>s</I> to <I>v</I>.<P>
Thus, we must have <img src="../images/scrptf12.gif">[<I>u</I>, <I>v</I>] = <I>c</I>(<I>u</I>, <I>v</I>), which means (<I>u</I>, <I>v</I>) <img src="../images/notmem.gif"> <I>E</I><img src="../images/scrptf12.gif"><SUB></SUB>. Now, the augmenting path <I>p</I> that was chosen in <I>G</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/scrptf12.gif"><SUB></FONT></SUB> to produce <I>G</I><img src="../images/scrptf12.gif"><I>'<SUB></I></SUB> must contain the edge (<I>v</I>, <I>u</I>)<I> </I>in the direction from v to u<I>, </I>since (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/scrptf12.gif"><I>'</I></FONT><SUB></SUB>, (by supposition) and (<I>u</I>, <I>v</I>) <img src="../images/notmem.gif"> <I>E</I><img src="../images/scrptf12.gif"><SUB></SUB> as we have just shown. That is, augmenting flow along the path <I>p</I> pushes flow <I>back</I> along (<I>u</I>, <I>v</I>), and <I>v</I> appears before <I>u</I> on <I>p</I>. Since <I>p </I>is a shortest path from <I>s</I> to <I>t</I>, its subpaths are shortest paths (Lemma 25.1), and thus we have <img src="../images/delta12.gif"><I><SUB><FONT FACE="Courier New" SIZE=2></SUB><img src="../images/scrptf12.gif"></FONT><SUB>(</I>s, u<I>) = <img src="../images/delta12.gif"></I><img src="../images/scrptf12.gif"></SUB>(<I>s</I>, <I>v</I>) + 1. Consequently,<P>
<pre><img src="../images/delta12.gif"><I><SUB></SUB><img src="../images/scrptf12.gif"><SUB>(</I>s<I>, </I>v<I>)  =  <img src="../images/delta12.gif"></I></SUB><SUB><img src="../images/scrptf12.gif"></SUB>(<I>s</I>, <I>u</I>) - 1</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">  <img src="../images/delta12.gif"><I><SUB></I></SUB><img src="../images/scrptf12.gif"><SUB><I></SUB>'<SUB>(</I>s, u<I>) - 1</I></sub></sup></pre><P>
<pre>=  <img src="../images/delta12.gif"><I><img src="../images/scrptf12.gif">'(</I>s<I>, </I>v<I>) - 2</I></sub></sup></pre><P>
<pre>&lt;  <img src="../images/delta12.gif"><I><img src="../images/scrptf12.gif">'(</I>s<I>, </I>v<I>) ,</I></sub></sup></pre><P>
which contradicts our initial assumption.      <P>
The next theorem bounds the number of iterations of the Edmonds-Karp algorithm.<P>
<a name="0902_18c8">Theorem 27.9<a name="0902_18c8"><P>
If the Edmonds-Karp algorithm is run on a flow network <I>G</I> = (<I>V, E</I>) with source <I>s</I> and sink <I>t</I>, then the total number of flow augmentations performed by the algorithm is at most <I>O</I>(<I>V E</I>).<P>
<a name="0902_18c2"><a name="0902_18c3"><I><B>Proof     </I></B>We say that an edge (<I>u</I>, <I>v</I>) in a residual network <I>G</I><img src="../images/scrptf12.gif"> is <I><B>critical</I></B> on an augmenting path <I>p</I> if the residual capacity of <I>p</I> is the residual capacity of (<I>u</I>, <I>v</I>), that is, if <I>c<SUB><FONT FACE="Courier New" SIZE=2></I></SUB><img src="../images/scrptf12.gif"></FONT><I><SUB>(</I>p<I>) = </I>c<I><img src="../images/scrptf12.gif"></SUB>(</I>u<I>, </I>v<I>). </I>After we have augmented flow along an augmenting path, any critical edge on the path disappears from the residual network. Moreover, at least one edge on any augmenting path must be critical.<P>
Let <I>u</I> and <I>v</I> be vertices in <I>V</I> that are connected by an edge in <I>E</I>. How many times can (<I>u</I>, <I>v</I>) be a critical edge during the execution of the Edmonds-Karp algorithm? Since augmenting paths are shortest paths, when (<I>u</I>, <I>v</I>) is critical for the first time, we have<P>
<pre><img src="../images/delta12.gif"><I><SUB></SUB><img src="../images/scrptf12.gif"><SUB>(</I>s<I>, </I>v<I>) = <img src="../images/delta12.gif"></I></SUB><SUB><img src="../images/scrptf12.gif"></SUB>(<I>s</I>, <I>u</I>) + 1 .</sub></sup></pre><P>
Once the flow is augmented, the edge (<I>u</I>, <I>v</I>) disappears from the residual network. It cannot reappear later on another augmenting path until after the net flow from <I>u</I> to <I>v</I> is decreased, and this only happens if (<I>v</I>, <I>u</I>) appears on an augmenting path. If <img src="../images/scrptf12.gif"><I>'</I> is the flow in <I>G</I> when this event occurs, then we have<P>
<pre><img src="../images/delta12.gif"><I><img src="../images/scrptf12.gif">'(</I>s, u<I>) = <img src="../images/delta12.gif"></I><img src="../images/scrptf12.gif"><I>'</I>(<I>s</I>, <I>v</I>) + 1.</sub></sup></pre><P>
Since <img src="../images/delta12.gif"><I><img src="../images/scrptf12.gif"><SUB>(</I>s<I>, </I>v<I>) <img src="../images/lteq12.gif"> <img src="../images/delta12.gif"></I></SUB><FONT FACE="Courier New" SIZE=2><SUB><img src="../images/scrptf12.gif"></SUB>'</FONT>(s, <I>v</I>) by Lemma 27.8, we have<P>
<pre><img src="../images/delta12.gif"><img src="../images/scrptf12.gif">'(<I>s</I>, <I>u</I>)  =  <img src="../images/delta12.gif"><img src="../images/scrptf12.gif">'(<I>s</I>, <I>v</I>) + 1</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  <img src="../images/delta12.gif"><img src="../images/scrptf12.gif">(<I>s</I>, <I>v</I>) + 1</sub></sup></pre><P>
<pre>=  <img src="../images/delta12.gif"><img src="../images/scrptf12.gif">(<I>s</I>, <I>u</I>) + 2.</sub></sup></pre><P>
Consequently, from the time (<I>u</I>, <I>v</I>) becomes critical to the time when it next becomes critical, the distance of <I>u</I> from the source increases by at least 2. The distance of <I>u</I> from the source is initially at least 1, and until it becomes unreachable from the source, if ever, its distance is at most <img src="../images/sglvrt.gif"><I>V</I><img src="../images/sglvrt.gif"><I></I> - 2. Thus, (<I>u</I>, <I>v</I>) can become critical at most <I>O</I>(<I>V</I>)