Successive shortest paths

Abstract view

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. The balance discrepancy of each node [math]\displaystyle{ v\in V }[/math] is underestimating, that is,

Variant: The balance discrepancy strictly decreases, that is, the value

[math]\displaystyle{ \sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right| }[/math].

Induction basis:

Abstract view: Start with an arbitrary value <math>f(a)\in[0\ldots u(a)