Successive shortest paths

Abstract view

Definition:

1. The imbalance of a node [math]\displaystyle{ v\in V }[/math] is defined as [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v) }[/math].
2. The imbalance of a node [math]\displaystyle{ v\in V }[/math] is underestimating if:
   1. If [math]\displaystyle{ b(v)\gt 0 }[/math], then [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\leq b(v) }[/math].
   2. If [math]\displaystyle{ b(v)\lt 0 }[/math], then [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\geq b(v) }[/math].
   3. If [math]\displaystyle{ b(v)=0 }[/math], then [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v) }[/math].
3. The total imbalance is the sum of the absolute values of all imbalances, taken over all nodes.

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 ever node is underestimating.

Variant: The total imbalance strictly decreases.

Induction basis

Abstract view: Start with the zero flow.

Proof: Obvious.

Induction step

1. If there