Negative cycle-canceling: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 27: Line 27:
# Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm.
# Run an [[All pairs shortest paths|all-pairs shortest-paths]] algorithm.
# 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 distance is negative),
# Otherwise (that is, the distance is negative):

Revision as of 12:03, 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:

  1. Find a cycle of negative cost in the residual network.
  2. Augment the flow on all arcs of this cycle by the minmum residual capacity of all arcs on this cycle.

Implementation:

  1. Run an all-pairs shortest-paths algorithm.
  2. If the distance [math]\displaystyle{ v\rightarrow v }[/math] is 0 for all [math]\displaystyle{ v\in V }[/math], the break condition applies.
  3. Otherwise (that is, the distance is negative):