Edmonds-Karp: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(39 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== General Information ==
== General Information ==


'''Algorithmic problem:''' [[Max-Flow Problems]]
'''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problems (standard version)]]


'''Algorithm :''' This is a minor variation of [[Ford-Fulkerson]]: Among all flow-augmenting <math>(s,t)</math>-paths, always choose one with smallest number of arcs.
'''Algorithm :''' This is a specialization of [[Ford-Fulkerson]]: Among all [[Basic flow definitions#Flow augmenting paths and saturated arcs|flow-augmenting paths]] <math>(s,t)</math>-paths, always choose one with smallest number of arcs. Consequently, a [[Breadth-first search|BFS]] is applied to find the path.


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


'''Invariant:'''
'''Invariant:'''
After <math>i \ge 0</math> iterations:
identical to the invariant of [[Ford-Fulkerson]].
# The flow <math>f</math> is a fleasible flow.
# If all upper bounds are integral, <math>f</math> is integral as well.


'''Notation:'''
'''Notation:'''
Line 16: Line 14:


'''Variant:'''
'''Variant:'''
# The smallest number of arcs on a flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously.
# The smallest number of arcs on any flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously.
# Whenever that number does ''not'' decrease in an iteration, the size of <math>A_f</math> decreases.
# Whenever that number does ''not'' increase in an iteration, the size of <math>A_f</math> decreases in that iteration.


'''Break condition:''' There is no flow-augumenting path.
'''Break condition:''' There is no flow-augumenting path.
== Correctness ==
The [[Ford-Fulkerson#Correctness|correctness proof of Ford-Fulkerson]] proves the invariant. So, we have to show the variant. In the following, we focus on the [[Basic flow definitions#Residual network|residual network]] <math>(G_f,u_f)</math>.
Let <math>p</math> be the flow-augmenting path in the current iteration, and let <math>k</math> be the number of arcs on <math>p</math>; in other words, the minimum number of arcs of a flow-augmenting <math>(s,t)</math>-path with respect to the current flow. At least one arc of <math>p</math> will be saturated in this iteration and, thus, leave the residual network. Therefore, it remains to show that augmenting the flow along <math>p</math> according to [[Ford-Fulkerson]] does not create new flow-augmenting paths of length <math>k</math> or less than <math>k</math>.
A new flow-augmenting <math>(s,t)</math>-path can only be created if a new arc enters the residual network. This must be an arc <math>(w,v)</math> such that <math>(v,w)</math> is an arc of <math>p</math>.
Suppose a new flow-augmenting path <math>p'</math> has been created. We have to show that <math>p'</math> has more than <math>k</math> arcs. Then <math>p'</math> contains <math>r\geq 1</math> arcs as specified in the last paragraph (that is, arcs opposite to arcs on <math>p</math>). Let <math>(w_1,v_1),\ldots,(w_r,v_r)</math> denote these arcs, in the order in which they appear on <math>p'</math> (not necessarily the order in which the opposite arcs appear on <math>p</math>). For notational convenience, let <math>v_0:=s</math> and <math>w_{r+1}:=t</math>.
For <math>i\in\{0,\ldots,r\}</math>, let <math>p_i</math> denote the subpath of <math>p'</math> from <math>v_i</math> to <math>w_{i+1}</math>. Now, for all paths <math>p_i</math> such that <math>w_{i+1}</math> appears after <math>v_i</math> on <math>p</math>, the specific choice of <math>p</math> to have a minimum number of arcs implies that <math>p_i</math> does not have fewer arcs than the subpath of <math>p</math> from <math>v_i</math> to <math>w_{i+1}</math>. For the other subpaths <math>p_i</math>, it suffices to note the trivial fact that the number of arcs on <math>p_i</math> is not negative. Note that for each arc <math>a</math> on <math>p</math>, there is at least one <math>i\in\{1,\ldots,r\}</math> such that <math>v_i</math> precedes <math>a</math> on <math>p</math> and <math>w_{i+1}</math> succeeds <math>a</math> on <math>p</math>. So, summing up the numbers of arcs on all <math>p_i</math> and adding the number <math>r</math> of arcs <math>(w_i,v_i)</math> to get the number of arcs on <math>p'</math> proves the claim.


== Complexity ==
== Complexity ==


'''Statement:'''
'''Statement:'''
Even if the upper bounds are not integral, the asymptotic complexity is in <math>\mathcal{O}(nm^2)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.
In any case (even if the upper bounds are not integral), the asymptotic complexity is in <math>\mathcal{O}(nm^2)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.


'''Proof:'''
'''Proof:'''
The variant implies that the smallest number of arcs on a flow-augmenting path strictly increases after at most <math>m</math> iterations. This number is positive, but cannot be larger than <math>n-1</math>. Hence, the total number of iterations is in <math>\mathcal{O}(nm)</math>. The claim then follows from the fact that the complexity of an iteration is linear in the number of arcs.
'''Remark:'''
The number of nodes is irrelevant for the complexity of an iteration because at most <math>m</math> nodes are reachable from <math>s</math> (not including <math>s</math> itself).

Latest revision as of 12:34, 1 December 2015

General Information

Algorithmic problem: Max-flow problems (standard version)

Algorithm : This is a specialization of Ford-Fulkerson: Among all flow-augmenting paths [math]\displaystyle{ (s,t) }[/math]-paths, always choose one with smallest number of arcs. Consequently, a BFS is applied to find the path.

Abstract View

Invariant: identical to the invariant of Ford-Fulkerson.

Notation: For an [math]\displaystyle{ (s,t) }[/math]-flow, let [math]\displaystyle{ A_f }[/math] denote the set of all arcs that belong to at least one flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs.

Variant:

  1. The smallest number of arcs on any flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
  2. Whenever that number does not increase in an iteration, the size of [math]\displaystyle{ A_f }[/math] decreases in that iteration.

Break condition: There is no flow-augumenting path.

Correctness

The correctness proof of Ford-Fulkerson proves the invariant. So, we have to show the variant. In the following, we focus on the residual network [math]\displaystyle{ (G_f,u_f) }[/math].

Let [math]\displaystyle{ p }[/math] be the flow-augmenting path in the current iteration, and let [math]\displaystyle{ k }[/math] be the number of arcs on [math]\displaystyle{ p }[/math]; in other words, the minimum number of arcs of a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path with respect to the current flow. At least one arc of [math]\displaystyle{ p }[/math] will be saturated in this iteration and, thus, leave the residual network. Therefore, it remains to show that augmenting the flow along [math]\displaystyle{ p }[/math] according to Ford-Fulkerson does not create new flow-augmenting paths of length [math]\displaystyle{ k }[/math] or less than [math]\displaystyle{ k }[/math].

A new flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path can only be created if a new arc enters the residual network. This must be an arc [math]\displaystyle{ (w,v) }[/math] such that [math]\displaystyle{ (v,w) }[/math] is an arc of [math]\displaystyle{ p }[/math].

Suppose a new flow-augmenting path [math]\displaystyle{ p' }[/math] has been created. We have to show that [math]\displaystyle{ p' }[/math] has more than [math]\displaystyle{ k }[/math] arcs. Then [math]\displaystyle{ p' }[/math] contains [math]\displaystyle{ r\geq 1 }[/math] arcs as specified in the last paragraph (that is, arcs opposite to arcs on [math]\displaystyle{ p }[/math]). Let [math]\displaystyle{ (w_1,v_1),\ldots,(w_r,v_r) }[/math] denote these arcs, in the order in which they appear on [math]\displaystyle{ p' }[/math] (not necessarily the order in which the opposite arcs appear on [math]\displaystyle{ p }[/math]). For notational convenience, let [math]\displaystyle{ v_0:=s }[/math] and [math]\displaystyle{ w_{r+1}:=t }[/math].

For [math]\displaystyle{ i\in\{0,\ldots,r\} }[/math], let [math]\displaystyle{ p_i }[/math] denote the subpath of [math]\displaystyle{ p' }[/math] from [math]\displaystyle{ v_i }[/math] to [math]\displaystyle{ w_{i+1} }[/math]. Now, for all paths [math]\displaystyle{ p_i }[/math] such that [math]\displaystyle{ w_{i+1} }[/math] appears after [math]\displaystyle{ v_i }[/math] on [math]\displaystyle{ p }[/math], the specific choice of [math]\displaystyle{ p }[/math] to have a minimum number of arcs implies that [math]\displaystyle{ p_i }[/math] does not have fewer arcs than the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ v_i }[/math] to [math]\displaystyle{ w_{i+1} }[/math]. For the other subpaths [math]\displaystyle{ p_i }[/math], it suffices to note the trivial fact that the number of arcs on [math]\displaystyle{ p_i }[/math] is not negative. Note that for each arc [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math], there is at least one [math]\displaystyle{ i\in\{1,\ldots,r\} }[/math] such that [math]\displaystyle{ v_i }[/math] precedes [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math] and [math]\displaystyle{ w_{i+1} }[/math] succeeds [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math]. So, summing up the numbers of arcs on all [math]\displaystyle{ p_i }[/math] and adding the number [math]\displaystyle{ r }[/math] of arcs [math]\displaystyle{ (w_i,v_i) }[/math] to get the number of arcs on [math]\displaystyle{ p' }[/math] proves the claim.

Complexity

Statement: In any case (even if the upper bounds are not integral), the asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(nm^2) }[/math] in the worst case, where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math].

Proof: The variant implies that the smallest number of arcs on a flow-augmenting path strictly increases after at most [math]\displaystyle{ m }[/math] iterations. This number is positive, but cannot be larger than [math]\displaystyle{ n-1 }[/math]. Hence, the total number of iterations is in [math]\displaystyle{ \mathcal{O}(nm) }[/math]. The claim then follows from the fact that the complexity of an iteration is linear in the number of arcs.

Remark: The number of nodes is irrelevant for the complexity of an iteration because at most [math]\displaystyle{ m }[/math] nodes are reachable from [math]\displaystyle{ s }[/math] (not including [math]\displaystyle{ s }[/math] itself).