Blocking flow by Dinic: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 41: Line 41:
'''Proof:'''
'''Proof:'''
Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an <math>(s,t)</math>-path, and from the specific choice of <math>\Delta</math> (see the [[Ford-Fulkerson#Induction step|proof]] of the induction step of Ford-Fulkerson for details). Also, the specific choice of <matH>\Delta</math> ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.
Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an <math>(s,t)</math>-path, and from the specific choice of <math>\Delta</math> (see the [[Ford-Fulkerson#Induction step|proof]] of the induction step of Ford-Fulkerson for details). Also, the specific choice of <matH>\Delta</math> ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.
== Correctness ==


== Complexity ==
== Complexity ==
Line 48: Line 50:


'''Proof:'''
'''Proof:'''
Due to the variant, the number of iterations is linear in the number of arcs. The total number of backward steps of the search
Due to the variant, the number of iterations is linear in the number of arcs. The second modification of  the search ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The numbr of forward steps within one iteration is linear in the number of nodes.

Revision as of 04:43, 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 DFS from [math]\displaystyle{ s }[/math] with two modifications: (1) The search may terminate early, namely if [math]\displaystyle{ t }[/math] is seen; (2) whenever the search goes backwards from some node, this node and all of its incident arcs are removed from [math]\displaystyle{ G }[/math].
  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]\displaystyle{ p }[/math].
    3. For each arc [math]\displaystyle{ a }[/math] on [math]\displaystyle{ 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].

Proof: Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an [math]\displaystyle{ (s,t) }[/math]-path, and from the specific choice of [math]\displaystyle{ \Delta }[/math] (see the proof of the induction step of Ford-Fulkerson for details). Also, the specific choice of [math]\displaystyle{ \Delta }[/math] ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.

Correctness

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\cdot m) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math],

Proof: Due to the variant, the number of iterations is linear in the number of arcs. The second modification of the search ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The numbr of forward steps within one iteration is linear in the number of nodes.