Successive shortest paths with reduced costs: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
'''Invariant:''' | '''Invariant:''' | ||
# 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 node <math>v\in V</math>, there is a real number <math>\pi(v)</math> such that, for each arc <math>a=(v,w)\in A_f</math>, the '''reduced cost''' <math>c(a)-\pi(v)+\pi(w)</math> is nonnegative. | # For each node <math>v\in V</math>, there is a real number <math>\pi(v)</math> such that, 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. | ||
'''Definition:''' | '''Definition:''' | ||
| Line 15: | Line 15: | ||
'''Proof:''' | '''Proof:''' | ||
Obviously, <math>\pi\equiv 0</math> is consistent with <math>f\equiv 0</math>. | Obviously, <math>\pi\equiv 0</math> is consistent with <math>f\equiv 0</math>. | ||
== Induction step == | |||
'''Abstract view:''' | |||
# Determine a shortest path with respect to <math> | |||
== Complexity == | |||
'''Statement:''' | |||
The asymptotic complexity is in <math>\mathcal{O}(C\cdot n\cdot T(n))</math>, where | |||
Revision as of 18:00, 25 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:
- Determine a shortest path with respect to [math]\displaystyle{ == Complexity == '''Statement:''' The asymptotic complexity is in \lt math\gt \mathcal{O}(C\cdot n\cdot T(n)) }[/math], where