Negative cycle-canceling: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view == '''Algorithmic problem:''' Min-cost flow problem '''Type of algorithm:''' loop '''Invariant:''' The flow is feasible. '''Variant:''' The cost of th...") |
|||
| Line 9: | Line 9: | ||
'''Variant:''' The cost of the flow decreases. | '''Variant:''' The cost of the flow decreases. | ||
''Definition:''' | '''Definition:''' | ||
A cycle is '''negative''' if the sum of the cost values on all of its arcs is negative. | A cycle is '''negative''' if the sum of the cost values on all of its arcs is negative. | ||
Revision as of 04:36, 22 October 2014
Abstract view
Algorithmic problem: Min-cost flow problem
Type of algorithm: loop
Invariant: The flow is feasible.
Variant: The cost of the flow decreases.
Definition: A cycle is negative if the sum of the cost values on all of its arcs is negative.
Break condition: There is no more negative cycle in the residual network.
Induction basis
Abstract view: Start with an arbitrary feasible flow, for example, the zero flow.
Induction step
Abstract view:
- Find a cycle of negative cost in the residual network.
- Augme