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

Induction basis

Abstract view: Start with the zero flow.

Proof: Obvious.

Induction step

1. In the residual network of [math]\displaystyle{ f }[/math], find a shortest path [math]\displaystyle{ p }[/math] from the set of nodes [math]\displaystyle{ v\in V }[/math] with [math]\displaystyle{ I_f(v)\lt 0 }[/math] to the set of nodes [math]\displaystyle{ w\in V }[/math] with [math]\displaystyle{ I_f(v)\gt 0 }[/math].
2. Let [math]\displaystyle{ v_0 }[/math] be the node where [math]\displaystyle{ p }[/math] actually starts and [math]\displaystyle{ w_0 }[/math] the node where [math]\displaystyle{ p }[/math] actually ends.
3. Increase the flow on all arcs of [math]\displaystyle{ p }[/math] by the minimum of [math]\displaystyle{ |I_f(v_0)| }[/math], of [math]\displaystyle{ I_f(w_0)\gt 0 }[/math], and of the residual capacities of all arcs on [math]\displaystyle{ p }[/math].

Correctness

The variant follows from the fact that the amount by which the flow is increased in step 3 is strictly positive. The first and third points of the invariant result from the choice of this amount as the minimum of imbalances and residual capacities. Thus, it remains to show point 2 of the invariant.

By induction hypothesis, there were nonegative cycles immediately before the iteration. So, any negative cycle [math]\displaystyle{ C }[/math] must have been introduced by the flow augmentation along [math]\displaystyle{ p }[/math]. Such a cycle must contain at least one arc [math]\displaystyle{ (v,w) }[/math] on [math]\displaystyle{ p }[/math] such that the residual capacity [math]\displaystyle{ w\rightarrow v }[/math] was zero immediately before the current iteration (and is positive afterwards, of course). Suppose for a contradiction that a negative cycle [math]\displaystyle{ C }[/math] has been introduced.

Let [math]\displaystyle{ p_1,\ldots,p_k }[/math] denote the maximal subpaths of [math]\displaystyle{ p }[/math] whose internal nodes do not belong to [math]\displaystyle{ p }[/math]. In other words, each [math]\displaystyle{ p_i }[/math] starts and ends on [math]\displaystyle{ p }[/math] but does not share any further node with [math]\displaystyle{ p }[/math]. Now, for [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math], let [math]\displaystyle{ p'_i }[/math] denote

1. the corresponding subpath of [math]\displaystyle{ p }[/math] if the start node of [math]\displaystyle{ p_i }[/math] appears on [math]\displaystyle{ p }[/math] before its end node;
2. the corresponding subpath of the transpose of [math]\displaystyle{ p }[/math] if the end node of [math]\displaystyle{ p_i }[/math] appears on [math]\displaystyle{ p }[/math] before its start node.

Further, let [math]\displaystyle{ C' }[/math] be the cycle that results from [math]\displaystyle{ C }[/math] when each subpath [math]\displaystyle{ p_i }[/math] is replaced by the corresponding subpath [math]\displaystyle{ p'_i }[/math] of [math]\displaystyle{ p }[/math] (in the first case) or of the transpose of [math]\displaystyle{ p }[/math] (in the second case). In general, this cycle is extremely non-simple. It contains each arc of [math]\displaystyle{ p }[/math] as often as its opposite arc. Threfore, the total cost of [math]\displaystyle{ C' }[/math] ist zero. Now it suffices to show that the total cost of [math]\displaystyle{ C }[/math] is not smaller than the total cost of [math]\displaystyle{ C' }[/math].

More specifically, for each [math]\displaystyle{ i\in\{1,\ldots,k\} }[/math], we will show that the cost of [math]\displaystyle{ p_i }[/math] is not smaller than the cost of [math]\displaystyle{ p'_i }[/math]. Note that all arcs on all subpaths [math]\displaystyle{ p_i }[/math] are in the residual network immediately before and immediately after the current iteration (with positive residual capacity, by definition). We apply the case distinction in the definition of [math]\displaystyle{ p'_i }[/math] above.

1. For a path [math]\displaystyle{ p_i }[/math] of the first type, the fact hat [math]\displaystyle{ p }[/math] is a shortest path implies that [math]\displaystyle{ p_i }[/math] is the shortest path from its start node to its end node
2. For a path [math]\displaystyle{ p_i }[/math] of the second type, let [math]\displaystyle{ p'' }[/math] denote the transpose of [math]\displaystyle{ p'_i }[/math]. In particular, [math]\displaystyle{ p''_i }[/math] is a subpath of [math]\displaystyle{ p }[/math]. Note that [math]\displaystyle{ p_i }[/math] and [math]\displaystyle{ p''_i }[/math] form a cycle, and that this cycle was augmenting immediately before the current iteration. By induction hypothesis, this cycle is not negative, [math]\displaystyle{ c(p_i)+c(p''_i)\geq 0 }[/math]. The claim now follows from [math]\displaystyle{ c(p'_i)=-c(p''_i) }[/math].