Successive shortest paths with reduced costs: Difference between revisions
Jump to navigation
Jump to search
| Line 20: | Line 20: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
# In the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>, find a shortest path <math>p</math> from the set of nodes <math>v\in V</math> with <math>I_f(v)<0</math> to the set of nodes <math>w\in V</math> with <math>I_f(v)>0</math> (cf. [[Successive shortest paths]] for the terminology). | # In the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>, find a shortest path <math>p</math> from the set of nodes <math>v\in V</math> with <math>I_f(v)<0</math> to the set of nodes <math>w\in V</math> with <math>I_f(v)>0</math> (cf. [[Successive shortest paths]] for the terminology). | ||
# Augment the current flow along this path by the | # Augment the current flow along this path by the minimum [[Basic flow definitions#Residual network|residual capacity]] of all arcs on this path. | ||
# Update the node labeling <math>\pi</math> such that it is consistent with the new flow. | # Update the node labeling <math>\pi</math> such that it is consistent with the new flow. | ||
'''Implementation of step 3:''' | '''Implementation of step 3:''' | ||
# Let <math>s</math> denote the start node of <math>p</math>. | |||
# For all nodes <math>v\in</math>: | |||
## Compute the shortest path length <math>\delta(v)</math> from <math>s</math> to <math>v</math>. | |||
## Set <math>\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 == | == Complexity == | ||
Revision as of 16:25, 26 October 2014
Abstract view
Invariant:
- All points of the invariant of the successive shortest paths algorithm.
- 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^\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: Obviously, [math]\displaystyle{ \pi\equiv 0 }[/math] is consistent with [math]\displaystyle{ f\equiv 0 }[/math].
Induction step
Abstract view:
- In the residual network of [math]\displaystyle{ f }[/math], find a shortest path [math]\displaystyle{ p }[/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).
- Augment the current flow along this path by the minimum residual capacity of all arcs on this path.
- Update the node labeling [math]\displaystyle{ \pi }[/math] such that it is consistent with the new flow.
Implementation of step 3:
- Let [math]\displaystyle{ s }[/math] denote the start node of [math]\displaystyle{ p }[/math].
- For all nodes [math]\displaystyle{ v\in }[/math]:
- Compute the shortest path length [math]\displaystyle{ \delta(v) }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math].
- 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