Successive shortest paths with reduced costs: Difference between revisions
Jump to navigation
Jump to search
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 | # 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. | ||
'''Definition:''' | |||
Such a node labeling <math>\pi</math> is called '''consistent''' with <math>f</math> in the following. | |||
== Induction basis == | == Induction basis == | ||
'''Abstract view:''' | |||
Start with the zero flow <math>f</math> and with a node labeling consistent with <math>f</math>. | |||
'''Implementation:''' | |||
# For all <math>a\in A</math>, set <math>f(a):=0</math>. | |||
# Generate a consistent | |||
Revision as of 16:07, 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(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 a node labeling consistent with [math]\displaystyle{ f }[/math].
Implementation:
- For all [math]\displaystyle{ a\in A }[/math], set [math]\displaystyle{ f(a):=0 }[/math].
- Generate a consistent