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: The induction step is a variation and extension of the induction step of the successive shortest paths algorithm. The essential modification is that [math]\displaystyle{ c }[/math] is replaced by [math]\displaystyle{ c^\pi }[/math]. Due to point 2 of the invariant, it is always [math]\displaystyle{ c^\pi\geq 0 }[/math]. Therefore, an efficient algorithm such as Dijkstra's may be applied. The extension is that, after each augmentation of the flow, the reduced cost values must be updated to maintain consistency.

Implementation of the update of the reduced cost values:

1. For every node [math]\displaystyle{ v\in V }[/math] that is not reachable from [math]\displaystyle{ s }[/math] in the residual network, add an arc [math]\displaystyle{ (s,v) }[/math] to [math]\displaystyle{ A }[/math] with a capacity at least as large as all original capacities and with zero cost.
2. Run a single-source shortest-paths algorithm with start node [math]\displaystyle{ s }[/math] and withe the current reduced cost values [math]\displaystyle{ c^\pi }[/math] as arc length.
3. For all original nodes [math]\displaystyle{ v\in V }[/math], set [math]\displaystyle{ \pi(v):=\pi(v)-\delta(v) }[/math], where [math]\displaystyle{ \delta(v) }[/math] is the distance of [math]\displaystyle{ v }[/math] computed in step 2.
4. Remove all arcs from [math]\displaystyle{ G }[/math] that were inserted in step 1.

Remark: The start node [math]\displaystyle{ s }[/math] could be an original node of [math]\displaystyle{ V }[/math]. However, if some nodes are not reachable from [math]\displaystyle{ s }[/math] in the residual network, arcs with large capacity and zero cost have to be inserted in [math]\displaystyle{ A }[/math] until all nodes are reachable from [math]\displaystyle{ s }[/math].

Proof: The variant and points 1 and 3 of the invariant of the successive shortest paths algorithm are obviously maintained. For point 2 of that invariant, it suffices to show that the shortest paths with respect to the arc lengths [math]\displaystyle{ c^\pi }[/math] are also shortest paths with respect to the arc lengths [math]\displaystyle{ c }[/math]; however, that results immediately from this statement.

It remains to show that the updated node potentials are consistent with the augmented flow. Let [math]\displaystyle{ \pi_\mathrm{before} }[/math] and [math]\displaystyle{ \pi_\mathrm{after} }[/math] denote the values of [math]\displaystyle{ \pi }[/math] immediately before and after the current iteration, respectively. Let [math]\displaystyle{ (v,w) }[/math] be an arc in the residual network of the augmented flow, that is, the flow immediately after the current iteration. We make a case distinction:

1. If [math]\displaystyle{ (v,w) }[/math] was also in the residual network immediately before the current iteration, the new reduced cost of [math]\displaystyle{ (v,w) }[/math] is [math]\displaystyle{ c^{\pi_\mathrm{after}}(v,w)=c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)=c(v,w)-\left[\pi_\mathrm{before}(v)-\delta(v)\right]+\left[\pi_\mathrm{before}(w)-\delta(w)\right]=c^{\pi_\mathrm{before}}(v,w)-\delta(w)+\delta(v) }[/math]. As the [math]\displaystyle{ \delta }[/math]-values are shortest-path distances with respect to arc lengths [math]\displaystyle{ c^{\pi_\mathrm{before}} }[/math], the valid distance property yields [math]\displaystyle{ \delta(w)\leq\delta(v)+c^{\pi_\mathrm{before}}(v,w) }[/math], which proves the claim.
2. Otherwise, [math]\displaystyle{ (w,v) }[/math] is on the shortest path computed in the current iteration. Recall [math]\displaystyle{ c(v,w)=-c(w,v) }[/math], so we obtain

[math]\displaystyle{ c^{\pi_\mathrm{after}}(v,w)= }[/math]

[math]\displaystyle{ c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)= }[/math]

[math]\displaystyle{ -\left[c(w,v)-\pi_\mathrm{after}(w)+\pi_\mathrm{after}(v)\right]= }[/math]

[math]\displaystyle{ -\left[c(w,v)-(\pi_\mathrm{before}(w)-\delta(w))+(\pi_\mathrm{before}(v)-\delta(v))\right]= }[/math]

[math]\displaystyle{ -\left[c^{\pi_\mathrm{before}}(w,v)-\delta(v)+\delta(w)\right] }[/math].

This statement proves that the last expression is zero.

Complexity

The asymptotic complexity and its proof are identical to the complexity considerations of the successive shortest paths algorithm.