Dinic: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 4: Line 4:


'''Type of algorithm :''' loop.
'''Type of algorithm :''' loop.
'''Break condition:''' There is no flow-augmenting <math>(s,t)</math>-path anymore.


== Abstract View ==
== Abstract View ==

Revision as of 13:47, 13 October 2014

General Information

Algorithmic problem: Max-Flow Problems

Type of algorithm : loop.

Break condition: There is no flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path anymore.

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations: The flow [math]\displaystyle{ f }[/math] is feasible. If all upper bounds are integral, the [math]\displaystyle{ f }[/math]-values are integral as well.

Variant: The smallest number of arcs on a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path strictly increases.

Induction basis

Abstract view: Initialize [math]\displaystyle{ f }[/math] as an arbitrary feasible flow, for example, the zero flow.

Proof: Nothing to show.

Induction step

Abstract view:

  1. Construct the subgraph [math]\displaystyle{ G'=(V,A') }[/math] of the residual network that contains an arc if, and only if, the arc is on at least one [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs.
  2. Construct a blocking flow [math]\displaystyle{ f' }[/math] in [math]\displaystyle{ G' }[/math] wth respect to the residual capacities for [math]\displaystyle{ f }[/math].
  3. For all arcs [math]\displaystyle{ a\in A }[/math], add [math]\displaystyle{ f' }[/math] to [math]\displaystyle{ f }[/math].