Successive shortest paths

Abstract view

Definition:

1. For a node [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ \delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v) }[/math].
2. The imbalance of a node [math]\displaystyle{ v\in V }[/math] is defined as [math]\displaystyle{ I_f(v):=\delta f(v)-b(v) }[/math].
3. The imbalance of a node [math]\displaystyle{ v\in V }[/math] is underestimating if [math]\displaystyle{ 0\leq\delta f(v)\leq b(v) }[/math] or [math]\displaystyle{ 0\geq\delta f(v)\geq b(v) }[/math].
4. The total imbalance of [math]\displaystyle{ f }[/math] is defined as [math]\displaystyle{ \sum_{v\in V}|I_f(v)| }[/math].

Invariant:

1. The capacity constraints are fulfilled, that is, [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
2. There is no negative cycle in the residual network of [math]\displaystyle{ f }[/math].
3. The imbalance of every node is underestimating.

Variant: The total imbalance strictly decreases.

Break condition: The imbalances of all nodes are zero or there is no augmenting path from some node [math]\displaystyle{ v\in V }[/math] with [math]\displaystyle{ I_f(v)\lt 0 }[/math] to any node [math]\displaystyle{ w }[/math] with [math]\displaystyle{ I_f(w)\gt 0 }[/math].

Induction basis

Abstract view: Start with the zero flow.

Proof: Obvious.

Induction step

1. Choose some node [math]\displaystyle{ s }[/math] with [math]\displaystyle{ I_f(s)\lt 0 }[/math] and some node [math]\displaystyle{ t }[/math] with [math]\displaystyle{ I_f(t)\gt 0 }[/math].
2. Find a shortest [math]\displaystyle{ (s,t) }[/math]-path [math]\displaystyle{ p }[/math].
3. If there is none, terminate the algorithm.
4. Increase the flow on all arcs of [math]\displaystyle{ p }[/math] by the minimum of the following three values: [math]\displaystyle{ |I_f(s)| }[/math], [math]\displaystyle{ I_f(t)\gt 0 }[/math], and the minimal residual capacity taken over all arcs on [math]\displaystyle{ p }[/math].

Remark: Since cost values may be negative in the residual network, step 2 requires an algorithm that copes with negative arc lengths. In particular, efficient algorithms such as Dijkstra's are not an option. However, a variant of the algorithm works on a nonnegative variation of the cost values, which allows efficient algorithms.

Proof:

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(B\cdot T) }[/math], where [math]\displaystyle{ B=\sum_{v\in V}|b(v)| }[/math], and [math]\displaystyle{ T }[/math] is the asymptotic complexity of the shortest-path algorithm.

Proof: Obviously, the number of iterations is in [math]\displaystyle{ \mathcal{O}(B) }[/math]. The complexity of an iteration is dominated by the shortest-path computation.