Blocking flow by Dinic: Difference between revisions
| Line 36: | Line 36: | ||
## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on <math>p</math>. | ## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on <math>p</math>. | ||
## For each arc <math>a</math> on <math>p</math>: | ## For each arc <math>a</math> on <math>p</math>: | ||
### Increase < | ### 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 <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, it is removed as well. | ### If the tail of <math>a</math> has no outgoing arcs anymore, it is removed as well. | ||
'''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>, 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. | |||
== Complexity == | |||
'''Statement:''' | |||
The asympütotic complexity is in <math>\mathcal{O}(n\cdot m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>, | |||
Revision as of 04:17, 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:
- Run a DFS from [math]\displaystyle{ s }[/math] that may terminate early, namely if [math]\displaystyle{ t }[/math] is seen.
- If [math]\displaystyle{ t }[/math] is not seen, the break condition applies, and the algorithm is terminated.
- Otherwise:
- Let [math]\displaystyle{ p }[/math] be the [math]\displaystyle{ (s,t) }[/math]-path found in step 1.
- 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].
- For each arc [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math]:
- Increase [math]\displaystyle{ f(a) }[/math] by [math]\displaystyle{ \Delta }[/math] and decrease [math]\displaystyle{ u(a) }[/math] by [math]\displaystyle{ \Delta }[/math].
- If [math]\displaystyle{ u(a)=0 }[/math], remove [math]\displaystyle{ a }[/math] from [math]\displaystyle{ G }[/math].
- If the tail of [math]\displaystyle{ a }[/math] has no outgoing arcs anymore, it is removed as well.
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], 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.
Complexity
Statement: The asympütotic complexity is in [math]\displaystyle{ \mathcal{O}(n\cdot m) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math],