Successive shortest paths with reduced costs: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view == '''Invariant:''' # All points of the invariant of the successive shortest paths algorithm. # For each node <math>v\in V</ma...") |
|||
| 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</math>, the '''reduced cost''' <math>c(a)-\pi(v)+\ | # 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</math>, the '''reduced cost''' <math>c(a)-\pi(v)+\pi(w)</math> is nonnegative. | ||
== Induction basis == | == Induction basis == | ||
Revision as of 17:58, 23 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 }[/math], the reduced cost [math]\displaystyle{ c(a)-\pi(v)+\pi(w) }[/math] is nonnegative.