Blocking flow by Dinic: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 11: Line 11:


'''Variant:'''
'''Variant:'''
The number of saturated arcs increases.
The number of arcs decreases.


'''Break condition:'''
'''Break condition:'''
There is no more [[Basic flow definitions#Flow-augmenting path|flow-augmenting]] ordinary <math>(s,t)</math>-path in <math>G</math> (that is, all arcs on the path are forward arcs).
There is no more [[Basic flow definitions#Flow-augmenting path|flow-augmenting]] ordinary <math>(s,t)</math>-path in <math>G</math> (that is, all arcs on the path are forward arcs).
== Induction basis ==
'''Abstract view:'''
Initialize <math>f</math> to be a feasible flow, for example, the zero flow.
'''Implementation:'''
Obvious.
'''Proof:'''
Obvious.
== Induction step ==
'''Abstract view:'''
# Run a modified [[Depth-first search|DFS]] from <math>s</math> that [[Graph traversal#Remarks|terminates early]] if <math>t</math> is seen.
# If <math>t</math> is not seen, the break condition applies, and the algorithm is terminated.
# Otherwise:
## Let <math>p</math> be the <math>(s,t)</math>-path found in step 1.
## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on </math>.
## For each arc <math>a<math> on <math>p</math>:
### Increase <matH>f(a)</math> by <math>\Delta</math> and decrease <math>u(a)</math> by <math>\Delta</math>.
### If <math>u(a)=0</math>, remove <math>a</math> from <math>G</math>.
### If the tail of <math>a</math> has no outgoing arcs anymore, <math> it is removed as well.

Revision as of 04:10, 20 October 2014

General information

Algorithmic problem: Blocking flow.

Type of algorithm: loop.

Abstract view

Invariant: The current flow is feasible.

Variant: The number of arcs decreases.

Break condition: There is no more flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math] (that is, all arcs on the path are forward arcs).

Induction basis

Abstract view: Initialize [math]\displaystyle{ f }[/math] to be a feasible flow, for example, the zero flow.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

  1. Run a modified DFS from [math]\displaystyle{ s }[/math] that terminates early if [math]\displaystyle{ t }[/math] is seen.
  2. If [math]\displaystyle{ t }[/math] is not seen, the break condition applies, and the algorithm is terminated.
  3. Otherwise:
    1. Let [math]\displaystyle{ p }[/math] be the [math]\displaystyle{ (s,t) }[/math]-path found in step 1.
    2. Let [math]\displaystyle{ \Delta }[/math] be the minimum of the values [math]\displaystyle{ u(a) }[/math] of all arcs [math]\displaystyle{ a }[/math] on </math>.
    3. For each arc [math]\displaystyle{ a\lt math\gt on \lt math\gt p }[/math]:
      1. Increase [math]\displaystyle{ f(a) }[/math] by [math]\displaystyle{ \Delta }[/math] and decrease [math]\displaystyle{ u(a) }[/math] by [math]\displaystyle{ \Delta }[/math].
      2. If [math]\displaystyle{ u(a)=0 }[/math], remove [math]\displaystyle{ a }[/math] from [math]\displaystyle{ G }[/math].
      3. If the tail of [math]\displaystyle{ a }[/math] has no outgoing arcs anymore, <math> it is removed as well.