Negative cycle-canceling: Difference between revisions
Jump to navigation
Jump to search
| Line 25: | Line 25: | ||
'''Implementation:''' | '''Implementation:''' | ||
# Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm. | # Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm on the [[Basic flow definitions#Residual network|residual network]], where the length of an arc <math>(v,w)in A</math> is defined as the minimum of <math>c(v,w)</math> and <math>-c(w,v)</math>. The number of all | ||
# If the distance <math>v\rightarrow v</math> is 0 for all <math>v\in V</math>, the break condition applies. | # If the distance <math>v\rightarrow v</math> is 0 for all <math>v\in V</math>, the break condition applies. | ||
# Otherwise (that is, the | # Otherwise (that is, the distances <math>v\rightarrow v</math> of some nodes <math>v\in V</math> are negative): | ||
## Reconstruct one negative cycle from the output of step 1. | |||
Revision as of 13:00, 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 on the residual network, where the length of an arc [math]\displaystyle{ (v,w)in A }[/math] is defined as the minimum of [math]\displaystyle{ c(v,w) }[/math] and [math]\displaystyle{ -c(w,v) }[/math]. The number of all
- If the distance [math]\displaystyle{ v\rightarrow v }[/math] is 0 for all [math]\displaystyle{ v\in V }[/math], the break condition applies.
- Otherwise (that is, the distances [math]\displaystyle{ v\rightarrow v }[/math] of some nodes [math]\displaystyle{ v\in V }[/math] are negative):
- Reconstruct one negative cycle from the output of step 1.