Successive shortest paths with reduced costs: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 22: Line 22:


'''Abstract view:'''
'''Abstract view:'''
# In the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>, find a shortest path <math>p</math> with respect to the arc lengths <math>c^\pi</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).
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 variation is that <math>c</math> is replaced by <math>c^\pi</math>. Due to 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.
# 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.


'''Implementation of step 3:'''
'''Implementation of the update of the reduced cost values:'''
# Let <math>s</math> denote the start node of <math>p</math>.
# Add a new node <math>s</math> to <math>V</math> and, for every node <math>v\in V</math>, an arc <math>(s,v)</math> to <math>A</math> with a capacity at least as large as all original capacities and with zero cost.
# For all nodes <math>v\in</math>:
# Run a [[Single source shortest paths|single-source shortest-paths algorithm]] with start node <math>s</math> and withe the current reduced cost values <math>c^\pi</math> as arc length.
## Compute the shortest path length <math>\delta(v)</math> from <math>s</math> to <math>v</math>.
# For all original 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> computed in step 2.
## Set <math>\pi(v):=\pi(v)-\delta(v)</math>.
# Remove <math>s</math> and all of its incident arcs from <math>G</math>.
 
'''Remark:'''
The start node <math>s</math> could be an original node of <math>V</math>. However, if some nodes are not reachable from <math>s</math> in the [[Basic flow definitions#Residual network|residual network]], arcs with large capacity and zero cost have to be inserted in <math>A</math> until all nodes are reachable from <math>s</math>.


'''Proof:'''
'''Proof:'''
The only non-obvious property is consistency of the node labeling computed in the implementation of step 3.
Points 1 and 3 of the invariant of the [[Successive shortest paths|successive shortest paths algorithm]] are obviously maintained.
 
For point 2 of that invariant,


== Complexity ==
== Complexity ==

Revision as of 13:45, 5 December 2014

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#successive shortest paths algorithm. The variation is that [math]\displaystyle{ c }[/math] is replaced by [math]\displaystyle{ c^\pi }[/math]. Due to 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. Add a new node [math]\displaystyle{ s }[/math] to [math]\displaystyle{ V }[/math] and, for every node [math]\displaystyle{ v\in V }[/math], 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 [math]\displaystyle{ s }[/math] and all of its incident arcs from [math]\displaystyle{ G }[/math].

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: Points 1 and 3 of the invariant of the successive shortest paths algorithm are obviously maintained.

For point 2 of that invariant,

Complexity

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

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Successive_shortest_paths_with_reduced_costs&oldid=2492"