Successive shortest paths

Abstract view

Invariant: The capacity constraints are fulfilled.

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