Successive shortest paths with reduced costs: Difference between revisions
m (→Abstract view: Vereinheitlichung Seitenaufbau) |
|||
| (29 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
== Abstract view == | == Abstract view == | ||
'''Algorithmic problem:''' [[Min-cost flow problem]] | |||
'''Type of algorithm:''' loop | |||
'''Auxiliary data:''' | '''Auxiliary data:''' | ||
| Line 7: | Line 11: | ||
# All points of the invariant of the [[Successive shortest paths|successive shortest paths]] algorithm. | # All points of the invariant of the [[Successive shortest paths|successive shortest paths]] algorithm. | ||
# For each arc <math>a=(v,w)\in A_f</math>, the '''reduced cost''' <math>c^\pi(a):=c(a)-\pi(v)+\pi(w)</math> is nonnegative. | # For each arc <math>a=(v,w)\in A_f</math>, the '''reduced cost''' <math>c^\pi(a):=c(a)-\pi(v)+\pi(w)</math> is nonnegative. | ||
'''Variant:''' The total imbalance strictly decreases. | |||
'''Definition:''' | '''Definition:''' | ||
Such a node labeling <math>\pi</math> is called '''consistent''' with <math>f</math> | Such a node labeling <math>\pi</math> is called '''consistent''' with <math>f</math>. | ||
== Induction basis == | == Induction basis == | ||
| Line 22: | Line 28: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
The induction step is a variation and extension of the [[Successive shortest paths#Induction step|induction step]] of the [[Successive shortest paths|successive shortest paths algorithm]]. The | The induction step is a variation and extension of the [[Successive shortest paths#Induction step|induction step]] of the [[Successive shortest paths|successive shortest paths algorithm]]. The essential modification is that <math>c</math> is replaced by <math>c^\pi</math>. Due to point 2 of the invariant, it is always <math>c^\pi\geq 0</math>. Therefore, an efficient algorithm such as [[Dijkstra|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: | '''Implementation''' of the update of the reduced cost values: | ||
For all nodes <math>v\in V</math>, set <math>\pi(v):=\pi(v)-\delta(v)</math>, where <math>\delta(v)</math> is the distance of <math>v</math> from <math>s</math> as computed in the [[Successive shortest paths#Induction step|induction step]] of the [[Successive shortest paths|successive shortest paths algorithm]]. | |||
'''Proof:''' | '''Proof:''' | ||
| Line 37: | Line 37: | ||
It remains to show that the updated node potentials are consistent with the augmented flow. Let <math>\pi_\mathrm{before}</math> and <math>\pi_\mathrm{after}</math> denote the values of <math>\pi</math> immediately before and after the current iteration, respectively. Let <math>(v,w)</math> be an arc in the [[Basic flow definitions#Residual network|residual network]] of the augmented flow, that is, the flow immediately after the current iteration. We make a case distinction: | It remains to show that the updated node potentials are consistent with the augmented flow. Let <math>\pi_\mathrm{before}</math> and <math>\pi_\mathrm{after}</math> denote the values of <math>\pi</math> immediately before and after the current iteration, respectively. Let <math>(v,w)</math> be an arc in the [[Basic flow definitions#Residual network|residual network]] of the augmented flow, that is, the flow immediately after the current iteration. We make a case distinction: | ||
# If <math>(v,w)</math> was also in the residual network immediately before the current iteration, the new reduced cost of <math>(v,w)</math> is <math>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>\delta</math>-values are shortest-path distances with respect to arc lengths <math>c^{\pi_\mathrm{before}}</math>, the [[basics of shortest paths#Valid distance property|valid distance property]] yields <math>\delta(w)\leq\delta(v)+c^{\pi_\mathrm{before}}(v,w)</math>, which proves the claim. | # If <math>(v,w)</math> was also in the residual network immediately before the current iteration, the new reduced cost of <math>(v,w)</math> is <math>c^{\pi_\mathrm{after}}(v,w)</math> <math> =c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)</math> <math>=c(v,w)-\left[\pi_\mathrm{before}(v)-\delta(v)\right]+\left[\pi_\mathrm{before}(w)-\delta(w)\right]</math> <matH>=c^{\pi_\mathrm{before}}(v,w)-\delta(w)+\delta(v)</math>. As the <math>\delta</math>-values are shortest-path distances with respect to arc lengths <math>c^{\pi_\mathrm{before}}</math>, the [[basics of shortest paths#Valid distance property|valid distance property]] yields <math>\delta(w)\leq\delta(v)+c^{\pi_\mathrm{before}}(v,w)</math>, which proves the claim. | ||
# Otherwise, <math>(w,v)</math> is on the shortest path computed in the current iteration. Recall <math>c(v,w)=-c(w,v)</math>, so we obtain <math>c^{\pi_\mathrm{after}}(v,w)=c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)=-\left[c(w,v)-\pi_\mathrm{after}(w)+\pi_\mathrm{after}(v)\right]=</math>. | # Otherwise, <math>(w,v)</math> is on the shortest path computed in the current iteration. Recall <math>c(v,w)=-c(w,v)</math>, so we obtain <math>c^{\pi_\mathrm{after}}(v,w)</math> <math>=c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w)</math> <math>=-\left[c(w,v)-\pi_\mathrm{after}(w)+\pi_\mathrm{after}(v)\right]</math> <math>=-\left[c(w,v)-(\pi_\mathrm{before}(w)-\delta(w))+(\pi_\mathrm{before}(v)-\delta(v))\right]</math> <math>=-\left[c^{\pi_\mathrm{before}}(w,v)-\delta(v)+\delta(w)\right]</math>. [[Basics of shortest paths#Distances along shortest paths|This statement]] proves that the last expression is zero. | ||
== Correctness == | |||
Cf. [[Successive shortest paths#Correctness|here]]. | |||
== Complexity == | == Complexity == | ||
The asymptotic complexity and its proof are identical to the [[Successive shortest paths#Complexity|complexity considerations]] of the [[Successive shortest paths|successive shortest paths algorithm]]. Note that <math>T</math> may now be the asymptotic complexity of an algorithm that cannot handle negative arc weights. | |||
The asymptotic complexity | |||
Latest revision as of 14:39, 20 February 2015
Abstract view
Algorithmic problem: Min-cost flow problem
Type of algorithm: loop
Auxiliary data: For each node [math]\displaystyle{ v\in V }[/math], there is a real number [math]\displaystyle{ \pi(v) }[/math].
Invariant:
- All points of the invariant of the successive shortest paths algorithm.
- 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.
Variant: The total imbalance strictly decreases.
Definition: Such a node labeling [math]\displaystyle{ \pi }[/math] is called consistent with [math]\displaystyle{ f }[/math].
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: For all 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] from [math]\displaystyle{ s }[/math] as computed in the induction step of the successive shortest paths algorithm.
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:
- 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) }[/math] [math]\displaystyle{ =c(v,w)-\pi_\mathrm{after}(v)+\pi_\mathrm{after}(w) }[/math] [math]\displaystyle{ =c(v,w)-\left[\pi_\mathrm{before}(v)-\delta(v)\right]+\left[\pi_\mathrm{before}(w)-\delta(w)\right] }[/math] [math]\displaystyle{ =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.
- 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.
Correctness
Cf. here.
Complexity
The asymptotic complexity and its proof are identical to the complexity considerations of the successive shortest paths algorithm. Note that [math]\displaystyle{ T }[/math] may now be the asymptotic complexity of an algorithm that cannot handle negative arc weights.