IT307
Network flow problems
By
K V Arya
Network flow problems
-
Introduction of:
network, max-flow problem
capacity, flow
Ford-Fulkerson method
pseudo code, residual networks, augmenting paths
cuts of networks
max-flow min-cut theorem
example of an execution
analysis, running time,
variations of the max-flow problem
Introduction network
Practical examples of a network
- liquids flowing through pipes
- parts through assembly lines
- current through electrical network
- information through communication network
- goods transported on the road
Introduction - network
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
v1
v3
v1
v2
v4
v3
source
v2
v4
sink
Introduction max-flow problem
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
v1
v3
v1
v2
v4
v3
source
v2
v4
sink
Informal definition of the max-flow problem:
What is the greatest rate at which material can be shipped from
the source to the sink without violating any capacity contraints?
Introduction - capacity
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3
v3
v1
8
3
6
v2
v4
6
12
c(u,v)=6
v2
v4
c(u,v)=12
v3
v1
Big pipe
v
Small pipe
Introduction - capacity
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3
v3
v1
8
3
6
v2
v4
If (u,v) E c(u,v) = 0
v2
v4
v1
6
0
0
0
v4
v3
v3
v2
v4
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3
v3
v1
8
v1
3
6
v2
v4
6
6/12
6/6
f(u,v)=6
v2
v4
f(u,v)=6
v3
Flow below capacity
v
Maximum flow
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3
v3
v1
8
3
6
v2
v1
v4
v3
v2
v4
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3
v3
v1
8
3
6/6
v2
v1
6/6
v4
6/8
v3
v2
v4
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3
v3
v1
8
3
6/6
v2
v1
6/6
v4
6/8
v3
v2
v4
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3/3
v3
v1
3/8
3/6
3
6/6
v2
v1
6/6
v4
6/8
v3
v2
v4
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3/3
v3
v1
3/8
3/6
3
6/6
v2
v1
6/6
v4
6/8
v3
v2
v4
Introduction flow
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3/3
v3
v1
5/8
2/3
3/6
3
6/6
v2
v1
6/6
v4
8/8
v3
v2
v4
Introduction cancellation
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3/3
v3
v1
5/8
2/3
3/6
3
6/6
v2
v1
6/6
v4
8/8
v3
v2
v4
Introduction cancellation
Representation
Example: oil pipeline
Flow network: directed graph G=(V,E)
3/3
v3
v1
6/8
3/3
4/6
S
6/6
v2
1/3
v4
5/6
8/8
u
10
v2
u
4
v3
v1
8/10
8/10
u
3/4
v4
5/10
Flow properties
Flow in G = (V,E): f: V x V R with 3 properties:
1) Capacity constraint: For all u,v V : f(u,v) < c(u,v)
2) Skew symmetry:
For all u,v V : f(u,v) = - f(v,u)
3) Flow conservation: For all u V \ {s,t} :
f(u,v) = 0
vV
Flow properties
Flow in G = (V,E): f: V x V R with 3 properties:
1) Capacity constraint: For all u,v V : f(u,v) < c(u,v)
For all u,v V : f(u,v) = - f(v,u)
2) Skew symmetry:
3) Flow conservation: For all u V \ {s,t} :
10
16
11/
v3
8/1
v2
11/14
v4
Note:
15
/20
by skew symmetry
t
4/9
12/12
1/4
v1
7/7
Flow network G = (V,E)
4/4
f(u,v) = 0
vV
f (v3,v1) = - 12
Net flow and value of a flow
Net Flow:
positive or negative value
of f(u,v)
u
8/10
u
3/4
5/10
f(u,v) = 5
4
f(v,u) = -5
3/3
v3
v1
Value of a Flow f:
Def:
|f| = v V f(s,v)
6/8
3/3
4/6
1/3
6/6
v2
5/6
v4
8/8
The max-flow problem
Informal definition of the max-flow problem:
What is the greatest rate at which material can be shipped from
the source to the sink without violating any capacity contraints?
Formal definition of the max-flow problem:
The max-flow problem is to find a valid flow for a given weighted
directed graph G, that has the maximum value over all valid
flows.
The Ford-Fulkerson method
a way how to find the max-flow
This method contains 3 important ideas:
1) residual networks
2) augmenting paths
3) cuts of flow networks
Ford-Fulkerson pseudo code
1 initialize flow f to 0
2 while there exits an augmenting path p
3
do augment flow f along p
4 return f
Ford Fulkerson residual networks
The residual network Gf of a given flow network G with a valid flow f
consists of the same vertices v V as in G which are linked with residual
edges (u,v) Ef that can admit more strictly positive net flow.
The residual capacity cf represents the weight of each edge Ef and is the
amount of additional net flow f(u,v) before exceeding the capacity c(u,v)
Flow network G = (V,E)
15
/20
8/1
3
v2
11/14
v4
4/4
v1
5
t
4/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
v3
11
5
8
cf(u,v) = c(u,v) f(u,v)
v2
v4
Ford Fulkerson residual networks
The residual network Gf of a given flow network G with a valid flow f
consists of the same vertices v V as in G which are linked with residual
edges (u,v) Ef that can admit more strictly positive net flow.
The residual capacity cf represents the weight of each edge Ef and is the
amount of additional net flow f(u,v) before exceeding the capacity c(u,v)
8/1
3
v2
11/14
v4
4/4
5
8
15
v2
3
11
cf(u,v) = c(u,v) f(u,v)
11
11
v3
5
t
12
v1
15
/20
4/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
Flow network G = (V,E)
v4
Ford Fulkerson augmenting paths
Definition: An augmenting path p is a simple (free of any cycle) path from s to
t in the residual network Gf
Residual capacity of p
cf(p) = min{cf (u,v): (u,v) is on p}
8/1
3
v2
11/14
v4
4/4
5
8
15
t
11
11
v3
5
t
12
v1
15
/20
4/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
Flow network G = (V,E)
v2
3
11
v4
Ford Fulkerson augmenting paths
Definition: An augmenting path p is a simple (free of any cycle) path from s to
t in the residual network Gf
Residual capacity of p
cf(p) = min{cf (u,v): (u,v) is on p}
8/1
3
v2
11/14
v4
4/4
5
8
15
t
11
11
v3
5
t
12
v1
15
/20
4/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
Flow network G = (V,E)
v2
v4
11
Augmenting path
Ford Fulkerson augmenting paths
We define a flow: fp: V x V R such as:
cf(p)
fp(u,v) =
if (u,v) is on p
- cf(p) if (v,u) is on p
otherwise
8/1
3
v2
11/14
v4
4/4
5
8
15
t
11
11
v3
5
t
12
v1
15
/20
4/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
Flow network G = (V,E)
v2
3
11
v4
Ford Fulkerson augmenting paths
We define a flow: fp: V x V R such as:
cf(p)
fp(u,v) =
if (u,v) is on p
- cf(p) if (v,u) is on p
otherwise
8/1
3
v2
11/14
v4
4/4
-4/
8
v2
4/5
11
11
v3
4/4
5
t
12
v1
-4
/5
15
/20
4/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
Flow network G = (V,E)
v4
11
Our virtual flow fp along the
augmenting path p in Gf
4/5
-4/
15
Ford Fulkerson augmenting the flow
We define a flow: fp: V x V R such as:
cf(p)
fp(u,v) =
if (u,v) is on p
- cf(p) if (v,u) is on p
otherwise
12/
1
New flow:
v2
11/14
v4
4/4
f: V x V R : f=f + fp
4/5
8
15
11
4/5
v3
4/4
/20
12
v1
11
19
0/9
v3
7/7
10
16
11/
12/12
1/4
v1
residual network Gf = (V,Ef)
Flow network G = (V,E)
v2
v4
11
Our virtual flow fp along the
augmenting path p in Gf
Ford Fulkerson new valid flow
proof of capacity constraint
cf(p)
Lemma:
f : V x V R : f = f + fp
in G
fp(u,v) =
0
if (u,v) is on p
- cf(p) if (v,u) is on p
otherwise
cf(p) = min{cf (u,v): (u,v) is on p}
Capacity constraint:
cf(u,v) = c(u,v) f(u,v)
For all u,v V, we require f(u,v) < c(u,v)
Proof:
fp (u ,v) < cf (u ,v) = c (u ,v) f (u ,v)
(f + fp) (u ,v) = f (u ,v) + fp (u ,v) < c (u ,v)
Ford Fulkerson new valid flow
proof of Skew symmetry
Lemma:
f : V x V R : f = f + fp
in G
Skew symmetry:
For all u,v V, we require f(u,v) = - f(v,u)
Proof:
(f + fp)(u ,v) = f (u ,v) + fp (u ,v) = - f (v ,u) fp (v ,u)
= - (f (v ,u) + fp (v ,u)) = - (f + fp) (v ,u)
Ford Fulkerson new valid flow
proof of flow conservation
Lemma:
f : V x V R : f = f + fp
in G
Flow conservation:
For all u V \ {s,t} :
f(u,v) = 0
vV
Proof:
u V {s ,t} (f + fp) (u ,v) = (f(u ,v) + fp (u ,v))
vV
= fv(u
,v) + fpv (uV ,v) = 0 + 0 = 0
V
vV
Ford Fulkerson new valid flow
Lemma:
| (f + fp) | = | f | + | fp |
Value of a Flow f:
Def:
|f| = v
f(s,v)
V
Proof:
| (f + fp) | = (f + fp) (s ,v) = (f (s ,v) + fp (s ,v))
vV
vV
= f (s ,v) + fp (s ,v) = | f | + | fp |
vV
vV
Ford Fulkerson new valid flow
Lemma:
f : V x V R : f = f + fp
in G
| (f + fp) | = | f | + | fp | > | f |
Lemma shows:
if an augmenting path can be found then the above flow
augmentation will result in a flow improvement.
Question: If we cannot find any more an augmenting path
is our flow then maximum?
Idea: The flow in G is maximum the residual Gf
contains no augmenting path.
Ford Fulkerson cuts of flow networks
New notion: cut (S,T) of a flow network
A cut (S,T) of a flow network G=(V,E) is a partiton of V into S and T
= V \ S such that s S and t T.
Practical example
v3
v2
v4
11/14
S
S = {s,v1,v2) , T = {v3,v4,t}
t
0/9
12/
1
In the example:
19
/20
7/7
1/4
10
16
11/
S
12/12
v1
Net flow f(S ,T) = f(v1,v3) + f(v2,v4) + f(v2,v3)
= 12 + 11 + (-0) = 23
4/4
Capacity c(S,T) = c(v1,v3) + c(v2,v4)
= 12 + 14 = 26
Implicit summation notation: f (S, T) = f (u, v)
uS
vT
Ford Fulkerson cuts of flow networks
Lemma:
the value of a flow in a network is the net flow across any cut of the
network
f (S ,T) = | f |
12/
1
proof
19
/20
t
0/9
v3
7/7
10
16
11/
12/12
1/4
v1
v2
11/14
v4
4/4
Ford Fulkerson cuts of flow networks
Assumption:
The value of any flow f in a flow network G is bounded from above
by the capacity of any cut of G
| f | < c (S, T)
< c (u, v)
u S v T
= c (S, T)
Hence, | f | < c (S, T)
v3
19
/20
7/7
u S v T
16
11/
12/12
0/9
= f (u, v)
v1
1/4
| f | = f (S, T)
10
Lemma:
12/
13
v2
11/14
v4
4/4
. Fulkerson: Max-flow min-cut theorem
If f is a flow in a flow network G = (V,E) with source s and sink t,
then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths.
3. | f | = c (S, T) for some cut (S, T) of G.
proof:
(2):
We assume for the sake of contradiction that f is a maximum flow in G but that
there still exists an augmenting path p in Gf.
Then as we know from above, we can augment the flow in G according to the
formula: f= f + fp. That would create a flow fthat is strictly greater than
the former flow f which is in contradiction to our assumption that f is a
maximum flow.
F. Fulkerson: Max-flow min-cut theorem
If f is a flow in a flow network G = (V,E) with source s and sink t,
then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths.
3. | f | = c (S, T) for some cut (S, T) of G.
proof:
original flow network G
(2) (3):
residual network Gf
3/3
v3
v1
6/8
3/3
4/6
S
6/6
v2
2
t
1/3
5/6
v4
8/8
v1
3
6
v3
4
2
6
5
v2
v4
F. Fulkerson: Max-flow min-cut theorem
If f is a flow in a flow network G = (V,E) with source s and sink t,
then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths.
3. | f | = c (S, T) for some cut (S, T) of G.
proof:
residual network Gf
(2) (3): Define
S = {v V | path p from s to v in Gf }
T = V \ S (note t S according to (2))
v1
2
3
6
v3
4
2
6
5
v2
v4
F. Fulkerson: Max-flow min-cut theorem
If f is a flow in a flow network G = (V,E) with source s and sink t,
then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths.
3. | f | = c (S, T) for some cut (S, T) of G.
proof:
original network G
(2) (3): Define
S = {v V | path p from s to v in Gf }
T = V \ S (note t S according to (2))
for u S, v T: f (u, v) = c (u, v)
(otherwise (u, v) Ef and v S)
| f | = f (S, T) = c (S, T)
3/3
v3
v1
6/8
3/3
4/6
1/3
6/6
v2
1
5/6
v4
8/8
F. Fulkerson: Max-flow min-cut theorem
If f is a fow in a flow network G = (V,E) with source s and sink t,
then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths.
3. | f | = c (S, T) for some cut (S, T) of G.
proof:
(3) (1): as proofed before | f | = f (S, T) < c (S, T)
the statement of (3) : | f | = c (S, T) implies that f is a maximum flow
The basic Ford Fulkerson algorithm
1 for each edge (u, v) E [G]
do f [u, v] = 0
2
3
f [v, u] = 0
4 while there exists a path p from s to t in the
residual network Gf
do cf (p) = min {cf (u, v) | (u, v) is in p}
5
for each edge (u, v) in p
6
do f [u, v] = f [u, v] + cf (p)
7
8
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
20
10
16
13
v2
14
v4
5
6
7
8
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
v3
0/2
0
t
0/9
0/4
0/10
6
0/1
S
0/12
v1
0/1
v2
0/14
v4
0/4
5
6
7
8
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
20
10
16
13
v2
14
v4
5
6
7
8
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
20
10
16
13
v2
14
v4
5
6
7
8
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
temporary variable:
cf (p) = 12
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
20
10
16
13
v2
14
v4
5
6
7
8
new flow network G
v1
12
/20
13
v2
14
v4
temporary variable:
t
v3
10
16
/
2
1
12/12
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
cf (p) = 12
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
13
v2
14
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
13
v2
14
v4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
13
v2
14
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
13
v2
14
v4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
13
v2
14
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
13
v2
14
v4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
13
v2
14
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
13
v2
14
v4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
temporary variable:
cf (p) = 4
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
13
v2
14
v4
5
6
7
8
new flow network G
v1
12
/20
4/1
v2
4/14
v4
temporary variable:
t
v3
10
16
/
2
1
12/12
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
cf (p) = 4
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
v2
10
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
4/1
v2
4/14
v4
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
v2
10
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
4/1
v2
4/14
v4
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
v2
10
v4
5
6
7
8
new flow network G
v1
12
/20
t
v3
10
16
/
2
1
12/12
4/1
v2
4/14
v4
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
v2
10
v4
5
6
7
8
new flow network G
v1
12
/20
4/1
v2
4/14
v4
temporary variable:
t
v3
10
16
/
2
1
12/12
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
cf (p) = 7
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
12
10
12
v2
10
v4
5
6
7
8
new flow network G
v3
19
/20
11/
13
v2
11/14
v4
temporary variable:
t
10
16
/
2
1
12/12
7/7
v1
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
cf (p) = 7
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
19
10
12
11
11
v2
v4
5
6
7
8
new flow network G
v3
19
/20
t
10
16
/
2
1
12/12
7/7
v1
11/
13
v2
11/14
v4
4/4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The basic Ford Fulkerson algorithm
example of an execution
1
2
3
4
(residual) network Gf
12
v1
v3
19
10
12
11
11
v2
v4
5
6
7
8
new flow network G
v3
19
/20
t
12/12
7/7
6
2/1
10
v1
11/
13
v2
11/14
v4
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
4/4
Finally we have:
| f | = f (s, V) = 23
Analysis of the Ford Fulkerson algorithm
unning time
1
2
3
4
5
6
7
8
for each edge (u, v) E [G]
do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
f [v, u] = - f [u, v]
The running time depends on how the augmenting path p in line 4 is determined.
Analysis of the Ford Fulkerson algorithm
Running time (arbitrary choice of p)
1
2
3
4
5
6
7
8
for each edge (u, v) E [G]
do f [u, v] = 0
O(|E|)
f [v, u] = 0
while there exists a path p from s to t
O(|E|)
in the residual network Gf
do cf(p) = min{cf(u, v) | (u, v) p}
for each edge (u, v) in p
do f [u, v] = f [u, v] + cf(p)
O(|E|)
f [v, u] = - f [u, v]
O(|E| |fmax|)
running time: O ( |E| |fmax| )
with fmax as maximum flow
(1) The augmenting path is chosen arbitrarily and all capacities are integers
Analysis of the Ford Fulkerson algorithm
Running time (arbitrary choice of p)
Consequencies of an arbitrarily choice:
Example if |f*| is large:
1 ,0
000
00 ,
1,0
00
, 00
v1
1, 0
00,
00 0
v2
1,0
0
,00
0
0
running time: O ( |E| |fmax| )
with fmax as maximum flow
(1) The augmenting path is chosen arbitrarily and all capacities are integers
Analysis of the Ford Fulkerson algorithm
Running time (arbitrary choice of p)
Consequencies of an arbitrarily choice:
residual network Gf
Example if |f*| is large:
v1
1,0
00
, 00
s
1, 0
00 ,
000
v2
9
,9 9
9
9
9
1/
0
1,0
1,0
00
, 00
t
00
0,0
v1
00
1/1
0
0 0,
0
,
/1
1, 0
00,
000
v2
,9
99
99
running time: O ( |E| |fmax| )
with fmax as maximum flow
(1) The augmenting path is chosen arbitrarily and all capacities are integers
Analysis of the Ford Fulkerson algorithm
Running time (arbitrary choice of p)
Consequencies of an arbitrarily choice:
residual network Gf
Example if |f*| is large:
v1
1/
1, 0
00
,00
s
1/
1,0
00 ,
000
v2
,9 9
99 9
1/
0
1,0
v1
t
00
0,0
99
9,9
9
0
/ 1,
00
0 0,
99 9
1
,99
9
v2
,9
99
99
running time: O ( |E| |fmax| )
with fmax as maximum flow
(1) The augmenting path is chosen arbitrarily and all capacities are integers
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Informal idea of the proof:
u1
(1) for all vertices v V\{s,t}:
v3
the shortest path distance f(s,v)
in Gf increases monotonically
with each flow augmentation
u2
v4
f (s,v) < f (s,v)
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Informal idea of the proof:
u1
(1) for all vertices v V\{s,t}:
. f(s,v) < f(s,v)
v3
the shortest path distance f(s,v)
in Gf increases monotonically
with each flow augmentation
u2
v4
f(s,u2) = 1
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Two flow augmentations later
Informal idea of the proof:
(1) for all vertices v V\{s,t}:
. f(s,v) < f(s,v)
v3
the shortest path distance f(s,v)
in Gf increases monotonically
with each flow augmentation
u1
u2
v4
f(s,u2) = 3
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
unning time with Edmonds-Karp algorithm
The total number of flow
augmentations performed by the
algorithm is at most O(|V| |E|)
u1
v3
u2
v4
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Def: critical edge (u,v)
u1
if cf(p) = cf(u,v)
How many times can (u,v) be
critical during an execution of
Edmonds-Karp algorithm?
At least one edge on p must be
critical.
v3
u2
v4
Critical edges on the path p
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Idea:
u1
(u,v) can become critical at most
O(V) times
v3
(After beeing critical it dissappears
in Gf and can only reappear after
net flow is decreased)
u2
v4
our example: edge (u2,v4)
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Two flow augmentations later
Idea:
(u,v) can become critical at most
O(V) times
v3
(After beeing critical it dissappears
in Gf and can only reappear after
net flow is decreased)
u1
u2
v4
our example: edge (u2,v4) has disappeared
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
After the third flow augmentation
Idea:
(u,v) can become critical at most
O(V) times
v3
(After beeing critical it disappears
in Gf and can only reappear after
net flow is decreased)
u1
u2
v4
our example: edge (u2,v4) reappeared
but is now unreachable from s
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
augmenting path is found by breath-first search and has to be a shortest path from p to t
Analysis of the Ford Fulkerson algorithm
Running time with Edmonds-Karp algorithm
Idea:
(u,v) can become critical at most
O(|V|) times
O(|E|) pairs of vertices exist in Gf
All critical edges in O(|V| |E|)
O(|E|) for breath first search for p
total running time O(|V| |E|)
running time: O ( |V| |E| )
(2) Edmonds-Karp algorithm
In Ford Fulkerson algorithm
If augmenting path is found by breath-first search and has to be a
shortest path from p to t then it become E-K algorithm
Different variants of the max-flow
problem
- The algorithm of Dinic (different implementations reaps better
running times than Edmonds-Karp): e.g. simultanous saturation of
augmenting paths of the same length O(|V| |E|)
-
A second capacity function lim for a lower limit of the flow
function f with lim(u,v) < f(u,v) < c(u,v)
A cost function cost where each edge (u,v) has got a second
weight cost(u,v) and the min-cost max-flow problem
Networks with multiple sources and sinks
Networks with multiple sources
and sinks
s1
8
T
t1
supersource
s2
8
s4
t2
s3
supersink
