Successive shortest paths with reduced costs

Abstract view

Auxiliary data: For each node [math]\displaystyle{ v\in V }[/math], there is a real number [math]\displaystyle{ \pi(v) }[/math].

Invariant:

1. All points of the invariant of the successive shortest paths algorithm.
2. For each arc [math]\displaystyle{ a=(v,w)\in A_f }[/math], the reduced cost [math]\displaystyle{ c^\pi(a):=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 the zero node labeling [math]\displaystyle{ \pi }[/math].

Proof: The assumption that all cost values are nonnegative implies that [math]\displaystyle{ \pi\equiv 0 }[/math] is consistent with [math]\displaystyle{ f\equiv 0 }[/math].

Induction step

Abstract view:

1. In the residual network of [math]\displaystyle{ f }[/math], find a shortest path [math]\displaystyle{ p }[/math] with respect to the arc lengths [math]\displaystyle{ c^\pi }[/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] (cf. Successive shortest paths for the terminology).
2. Augment the current flow along this path by the minimum residual capacity of all arcs on this path.
3. Update the node labeling [math]\displaystyle{ \pi }[/math] such that it is consistent with the new flow.

Implementation of step 3:

1. Let [math]\displaystyle{ s }[/math] denote the start node of [math]\displaystyle{ p }[/math].
2. For all nodes [math]\displaystyle{ v\in }[/math]:
   1. Compute the shortest path length [math]\displaystyle{ \delta(v) }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math].
   2. Set [math]\displaystyle{ \pi(v):=\pi(v)-\delta(v) }[/math].

Proof: The only non-obvious property is consistency of the node labeling computed in the implementation of step 3.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(C\cdot n\cdot T(n)) }[/math], where