Negative cycle-canceling

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:

1. Find a cycle of negative cost in the residual network.
2. Augment the flow on all arcs of this cycle by the minmum residual capacity of all arcs on this cycle.

Implementation:

1. 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
2. If the distance [math]\displaystyle{ v\rightarrow v }[/math] is 0 for all [math]\displaystyle{ v\in V }[/math], the break condition applies.
3. Otherwise (that is, the distances [math]\displaystyle{ v\rightarrow v }[/math] of some nodes [math]\displaystyle{ v\in V }[/math] are negative):
   1. Reconstruct one negative cycle [math]\displaystyle{ C }[/math] from the output of step 1.
   2. 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

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\tilder{f})\lt c(f) }[/math].

We will show that there are generalized cycles [math]\displaystyle{ C_1,\ldots,C_k }[/math] in [math]\displaystyle{ G }[/math] and [math]\displaystyle{ \varepsilon_1,\ldots,such that: # It is \lt math\gt \tilde{f}=f+\varepsilon_1\cdot C_1+\cdots+\varepsilon_k\cdot C_k }[/math].

1. 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.

Once