Negative cycle-canceling: Difference between revisions
Jump to navigation
Jump to search
| Line 22: | Line 22: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
# Find a [[Basic graph definitions#Cycles|cycle]] of negative cost in the [[Basic flow definitions#Residual network|residual network]]. | # Find a [[Basic graph definitions#Cycles|cycle]] of negative cost in the [[Basic flow definitions#Residual network|residual network]]. | ||
# | # Augment the flow on all arcs of this cycle by the minmum residual capacity of all arcs on this cycle. | ||
'''Implementation:''' | |||
# Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm. | |||
# | |||
Revision as of 07:35, 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.
- Augment the flow on all arcs of this cycle by the minmum residual capacity of all arcs on this cycle.
Implementation:
- Run an all-pairs shortest-paths algorithm.