Successive shortest paths with reduced costs

Abstract view

Invariant:

1. All points of the invariant of the successive shortest paths algorithm.
2. For each node [math]\displaystyle{ v\in V }[/math], there is a real number [math]\displaystyle{ \pi(v) }[/math] such that, for each arc [math]\displaystyle{ a=(v,w)\in A_f }[/math], the reduced cost [math]\displaystyle{ c(a)-\pi(v)+\pi(w) }[/math] is nonnegative.

Definition: Such a node labeling [math]\displaystyle{ \pi }[/math] is called consistent with [math]\displaystyle{ f }[/math] in the following.

Induction basis

Abstract view: Start with the zero flow [math]\displaystyle{ f }[/math] and with a node labeling consistent with [math]\displaystyle{ f }[/math].

Implementation:

1. For all [math]\displaystyle{ a\in A }[/math], set [math]\displaystyle{ f(a):=0 }[/math].
2. Generate a consistent