Negative cycle-canceling: Difference between revisions
| Line 42: | Line 42: | ||
To prove that, we apply an induction on the number <math>d</math> of arcs on which <math>f_1</math> and <math>f_2</math> differ. For <math>d=0</math>, nothing is to show. So suppose <math>d>0</math>. Let <math>(v_1,v_2)</math> be an arc on which <math>f_1</math> and <math>f_2</math> differ, say <math>f_1(v_1,v_2)<f_2(v_1,v_2)</math>. Then there is either an arc <math>(v_2,v_3)</math> with <math>f_1(v_2,v_3)<f_2(v_2,v_3)</math> or an arc <math>(v_3,v_2)</math> with <math>f_1(v_3,v_2)>f_2(v_3,v_2)</math>. This argument may be continued, so we obtain a sequence <math>v_1,v_2,v_3,v_4,\ldots</math> such that for all <math>i</math>, there is <math>(v_i,v_{i+1})</math> with <math>f_1(v_i,v_{i+1})<f_2(v_i,v_{i+1})</math> or <math>(v_{i+1},v_i)</math> with <math>f_1(v_{i+1},v_i)<f_2(v_{i+1},v_i)</math>. Since the number of nodes is finite, there must be <math>i</math> and <math>j</math> such that <math>v_i=v_j</math>. Therefore, a generalized cycle <math>C_1</math> is closed such that <math>f_1(a)<f_2(a)\leq u(a)</math> on each forward arc and <math>f_1(a)>f_2(a)\geq 0</math> on each backward arc. In particular, there is <math>\varepsilon_1>0</math> such that <math>f_1+\varepsilon_1\cdot C_1</math> is feasible. If <math>\varepsilon_1</math> is chosen maximal, <math>f_1+\varepsilon_1\cdot C_1</math> agrees one at least one more arc with <math>f_2</math> than <math>f_1</math>. Now the induction hypothesis proves the general fact. | To prove that, we apply an induction on the number <math>d</math> of arcs on which <math>f_1</math> and <math>f_2</math> differ. For <math>d=0</math>, nothing is to show. So suppose <math>d>0</math>. Let <math>(v_1,v_2)</math> be an arc on which <math>f_1</math> and <math>f_2</math> differ, say <math>f_1(v_1,v_2)<f_2(v_1,v_2)</math>. Then there is either an arc <math>(v_2,v_3)</math> with <math>f_1(v_2,v_3)<f_2(v_2,v_3)</math> or an arc <math>(v_3,v_2)</math> with <math>f_1(v_3,v_2)>f_2(v_3,v_2)</math>. This argument may be continued, so we obtain a sequence <math>v_1,v_2,v_3,v_4,\ldots</math> such that for all <math>i</math>, there is <math>(v_i,v_{i+1})</math> with <math>f_1(v_i,v_{i+1})<f_2(v_i,v_{i+1})</math> or <math>(v_{i+1},v_i)</math> with <math>f_1(v_{i+1},v_i)<f_2(v_{i+1},v_i)</math>. Since the number of nodes is finite, there must be <math>i</math> and <math>j</math> such that <math>v_i=v_j</math>. Therefore, a generalized cycle <math>C_1</math> is closed such that <math>f_1(a)<f_2(a)\leq u(a)</math> on each forward arc and <math>f_1(a)>f_2(a)\geq 0</math> on each backward arc. In particular, there is <math>\varepsilon_1>0</math> such that <math>f_1+\varepsilon_1\cdot C_1</math> is feasible. If <math>\varepsilon_1</math> is chosen maximal, <math>f_1+\varepsilon_1\cdot C_1</math> agrees one at least one more arc with <math>f_2</math> than <math>f_1</math>. Now the induction hypothesis proves the general fact. | ||
Finally, we are in a position to prove correctness of the algorithm. For that, we have to show that a feasible flow is minimum if it admits no negative cycle. So assume a feasible flow <math>f</math> is ''not'' minimum. Then there is a feasible flow <math>\tilde{f}</math> such that <math>c\tilde{f})<c(f)</math>. There are <math>C_1,\ldots,C_k</math> and <math>\varepsilon_1,\ldots,\varepsilon_k</math> as described above. Since <math>c(\tilde{f})<c(f)</math>, at least one of the cycles must be a negative one,say <math>C_i</math>. It is easy to see that the cycles may be permuted in the decomposition, so <math>f+\varepsilon_i\cdot C_i</math> is feasible (consistenc< is essential for that). This proves the claim. | Finally, we are in a position to prove correctness of the algorithm. For that, we have to show that a feasible flow is minimum if it admits no negative cycle. So assume a feasible flow <math>f</math> is ''not'' minimum. Then there is a feasible flow <math>\tilde{f}</math> such that <math>c(\tilde{f})<c(f)</math>. There are <math>C_1,\ldots,C_k</math> and <math>\varepsilon_1,\ldots,\varepsilon_k</math> as described above. Since <math>c(\tilde{f})<c(f)</math>, at least one of the cycles must be a negative one,say <math>C_i</math>. It is easy to see that the cycles may be permuted in the decomposition, so <math>f+\varepsilon_i\cdot C_i</math> is feasible (consistenc< is essential for that). This proves the claim. | ||
Revision as of 19:21, 22 October 2014
Abstract view
Algorithmic problem: Min-cost flow problem
Type of algorithm: loop
Invariant: The flow is feasible.
Variant: The cost of the flow decreases.
Definition: A cycle is negative if the sum of the cost values on all of its arcs is negative.
Break condition: There is no more negative cycle in the residual network.
Induction basis
Abstract view: Start with an arbitrary feasible flow, for example, the zero flow.
Induction step
Abstract view:
- Find a cycle of negative cost in the residual network.
- Augment the flow on all arcs of this cycle by the minmum residual capacity of all arcs on this cycle.
Implementation:
- Run an all-pairs shortest-paths algorithm on the residual network, where the length of an arc [math]\displaystyle{ (v,w)in A }[/math] is defined as the minimum of [math]\displaystyle{ c(v,w) }[/math] and [math]\displaystyle{ -c(w,v) }[/math]. The number of all
- If the distance [math]\displaystyle{ v\rightarrow v }[/math] is 0 for all [math]\displaystyle{ v\in V }[/math], the break condition applies.
- Otherwise (that is, the distances [math]\displaystyle{ v\rightarrow v }[/math] of some nodes [math]\displaystyle{ v\in V }[/math] are negative):
- Reconstruct one negative cycle [math]\displaystyle{ C }[/math] from the output of step 1.
- Augment the flow on all arcs of [math]\displaystyle{ C }[/math] (in the [Basic flow definitions#Residual network|residual network]]) by the minimum residual capacity of all arcs of [math]\displaystyle{ C }[/math].
Proof: The invariant and the variant are obviously fulfilled.
Correctness
First we will show a general fact: For two feasible flows, [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math], there are generalized cycles [math]\displaystyle{ C_1,\ldots,C_k }[/math] in [math]\displaystyle{ G }[/math] and [math]\displaystyle{ \varepsilon_1,\ldots,\varepsilon_k\gt 0 }[/math] such that:
- Decomposition of [math]\displaystyle{ f_2-f_1 }[/math]: It is [math]\displaystyle{ f_2=f_1+\varepsilon_1\cdot C_1+\cdots+\varepsilon_k\cdot C_k }[/math].
- Consistency: For each arc [math]\displaystyle{ a\in A }[/math] and [math]\displaystyle{ i,j\in\{1,\ldots,k\} }[/math]: If [math]\displaystyle{ a }[/math] belongs to [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math], then [math]\displaystyle{ a }[/math] is a forward arc on both cycles, or [math]\displaystyle{ a }[/math] is a backward arc in both cycles.
To prove that, we apply an induction on the number [math]\displaystyle{ d }[/math] of arcs on which [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math] differ. For [math]\displaystyle{ d=0 }[/math], nothing is to show. So suppose [math]\displaystyle{ d\gt 0 }[/math]. Let [math]\displaystyle{ (v_1,v_2) }[/math] be an arc on which [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math] differ, say [math]\displaystyle{ f_1(v_1,v_2)\lt f_2(v_1,v_2) }[/math]. Then there is either an arc [math]\displaystyle{ (v_2,v_3) }[/math] with [math]\displaystyle{ f_1(v_2,v_3)\lt f_2(v_2,v_3) }[/math] or an arc [math]\displaystyle{ (v_3,v_2) }[/math] with [math]\displaystyle{ f_1(v_3,v_2)\gt f_2(v_3,v_2) }[/math]. This argument may be continued, so we obtain a sequence [math]\displaystyle{ v_1,v_2,v_3,v_4,\ldots }[/math] such that for all [math]\displaystyle{ i }[/math], there is [math]\displaystyle{ (v_i,v_{i+1}) }[/math] with [math]\displaystyle{ f_1(v_i,v_{i+1})\lt f_2(v_i,v_{i+1}) }[/math] or [math]\displaystyle{ (v_{i+1},v_i) }[/math] with [math]\displaystyle{ f_1(v_{i+1},v_i)\lt f_2(v_{i+1},v_i) }[/math]. Since the number of nodes is finite, there must be [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] such that [math]\displaystyle{ v_i=v_j }[/math]. Therefore, a generalized cycle [math]\displaystyle{ C_1 }[/math] is closed such that [math]\displaystyle{ f_1(a)\lt f_2(a)\leq u(a) }[/math] on each forward arc and [math]\displaystyle{ f_1(a)\gt f_2(a)\geq 0 }[/math] on each backward arc. In particular, there is [math]\displaystyle{ \varepsilon_1\gt 0 }[/math] such that [math]\displaystyle{ f_1+\varepsilon_1\cdot C_1 }[/math] is feasible. If [math]\displaystyle{ \varepsilon_1 }[/math] is chosen maximal, [math]\displaystyle{ f_1+\varepsilon_1\cdot C_1 }[/math] agrees one at least one more arc with [math]\displaystyle{ f_2 }[/math] than [math]\displaystyle{ f_1 }[/math]. Now the induction hypothesis proves the general fact.
Finally, we are in a position to prove correctness of the algorithm. For that, we have to show that a feasible flow is minimum if it admits no negative cycle. So assume a feasible flow [math]\displaystyle{ f }[/math] is not minimum. Then there is a feasible flow [math]\displaystyle{ \tilde{f} }[/math] such that [math]\displaystyle{ c(\tilde{f})\lt c(f) }[/math]. There are [math]\displaystyle{ C_1,\ldots,C_k }[/math] and [math]\displaystyle{ \varepsilon_1,\ldots,\varepsilon_k }[/math] as described above. Since [math]\displaystyle{ c(\tilde{f})\lt c(f) }[/math], at least one of the cycles must be a negative one,say [math]\displaystyle{ C_i }[/math]. It is easy to see that the cycles may be permuted in the decomposition, so [math]\displaystyle{ f+\varepsilon_i\cdot C_i }[/math] is feasible (consistenc< is essential for that). This proves the claim.