CSE408

Maximum Flow
Maximum Flow

• Maximum Flow Problem

• The Ford-Fulkerson Method

Flow networks:

• A flow network G=(V,E): a directed graph, where each edge

(u,v)E has a nonnegative capacity c(u,v)>=0.
• If (u,v)E, we assume that c(u,v)=0.
• two distinct vertices :a source s and a sink t.

12

16 20

s 10 9 7 t
4

13 4

14
Flow:

• G=(V,E): a flow network with capacity function c.

• s-- the source and t-- the sink.
• A flow in G: a real-valued function f:V*V  R satisfying
the following two properties:
• Capacity constraint: For all u,v V,
we require f(u,v)  c( u,v).
• Flow conservation: For all u V-{s,t}, we require

 f (e)   f (e)
e.in.v e.out.v
Net flow and value of a flow f:

• The quantity f (u,v) is called the net flow from vertex

u to vertex v.
• The value of a flow is defined as

f   f ( s, v )
– The total flow fromvsource
V
to any other vertices.
– The same as the total flow from any vertices to
the sink.
 12/12

15/20
11/16

s 10 1/4 4/9 7/7 t

8/13 4/4

11/14

A flow f in G with value . f  19

Maximum-flow problem:

• Given a flow network G with source s and sink t

• Find a flow of maximum value from s to t.

• How to solve it efficiently?

The Ford-Fulkerson method:

• This section presents the Ford-Fulkerson method for solving

the maximum-flow problem.We call it a “method” rather than
an “algorithm” because it encompasses several
implementations with different running times.
• The Ford-Fulkerson method depends on three important
ideas that transcend the method and are relevant to many
flow algorithms and problems: residual networks,augmenting
paths,and cuts.
• These ideas are essential to the important max-flow min-cut
theorem,which characterizes the value of maximum flow in
terms of cuts of the flow network.
• FORD-FULKERSON-METHOD(G,s,t)
• initialize flow f to 0
• while there exists an augmenting path p
• do augment flow f along p
• return f
Residual networks:

• Given a flow network and a flow, the residual

network consists of edges that can admit more net
flow.
• G=(V,E) --a flow network with source s and sink t
• f: a flow in G.
• The amount of additional net flow from u to v
before exceeding the capacity c(u,v) is the residual
capacity of (u,v), given by: cf(u,v)=c(u,v)-f(u,v)
in the other direction: cf(v, u)=c(v, u)+f(u, v).
 Example of residual network

12 4/12
16 v1 v3 20 4/16 v1 v3 20

s 10 4 7 t s 7
9 10 4 t
4/9
13 4 13 4/4
v2 v4 v2 v4
14 4/14

(a)
 Example of Residual network (continued)

8
12
v1 v3 20
4
4
s 10 4 4
7 t
5
13 10 4
v2 v4
4

(b)
Fact 1:

• Let G=(V,E) be a flow network with source s and sink t, and let
f be a flow in G.
• Let Gf be the residual network of G induced by f,and let f’ be a
flow in Gf.Then, the flow sum f+f’ is a flow in G with
value .
f  in
• f+f’: the flow  fsame
f ' the  f 'direction will be added.
the flow in different directions will be cnacelled.
Augmenting paths:

• Given a flow network G=(V,E) and a flow f, an augmenting

path is a simple path from s to t in the residual network Gf.

• Residual capacity of p : the maximum amount of net flow that

we can ship along the edges of an augmenting path p, i.e.,
cf(p)=min{cf(u,v):(u,v) is on p}.

2 3 1

The residual capacity is 1.

 Example of an augment path (bold edges)

8
12
v1 v3 20
4
4
s 10 4 4
7 t
5
13 10 4
v2 v4
4

(b)
The basic Ford-Fulkerson algorithm:

• FORD-FULKERSON(G,s,t)
• 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) is in p}
• for each edge (u,v) in p
• do f[u,v] f[u,v]+cf(p)
•
Example:
• The execution of the basic Ford-Fulkerson algorithm.

• (a)-(d) Successive iterations of the while loop: The left side of

each part shows the residual network Gf from line 4 with a
shaded augmenting path p.
• The right side of each part shows the new flow f that results
from adding fp to f.
• The residual network in (a) is the input network G.(e) The
residual network at the last while loop test.
• It has no augmenting paths,and the flow f shown in (d) is
therefore a maximum flow.
 12 4/12
16 v1 v3 20 4/16 v1 v3 20

s 10 4 7 t s 7
9 10 4 t
4/9
13 4 13 4/4
v2 v4 v2 v4
14 4/14

(a)
 8
12 4/12
v1 v3 20 v1 v3 7/20
4 11/16
4
s 10 4 4
7 t s 7/10 4 7/7 t
5 4/9
13 10 4 13 4/4
v2 v4 v2 v4
4 11/14

(b)
 8 12/12
5 v1 v3 13
4 11/16 v1 v3 15/20
11 4
s 3 11 7 7 t s 7/7
10 1/4 t
5 4/9
13 3
4 8/13 4/4
v2 v4 v2 v4
11 11/14

(c)
 12 12/12
5 v1 v3 5 11/16 v1 v3 19/20
11 4
s 11 3 7 15 t s 7/7
5 10 1/4 t
5 9
8 3
4 12/13 4/4
v2 v4 v2 v4
11 11/14

(d)
 12
5 v1 v3 1

s 3 19
1 11 9 7 t

12 3 4
v2 v4
11

(e)
Time complexity:

• If each c(e) is an integer, then time complexity is O(|E|f*),

where f* is the maximum flow.
• Reason: each time the flow is increased by at least one.
• This might not be a polynomial time algorithm since f* can be
represented by log (f*) bits. So, the input size might be log(f*).
POLLING QUESTIONS

• What does Maximum flow problem involve?

a) finding a flow between source and sink that
is maximum
b) finding a flow between source and sink that
is minimum
c) finding the shortest path between source
and sink
d) computing a minimum spanning tree
• What is the source?
a) Vertex with no incoming edges
b) Vertex with no leaving edges
c) Centre vertex
d) Vertex with the least weight
• Which algorithm is used to solve a maximum
flow problem?
a) Prim’s algorithm
b) Kruskal’s algorithm
c) Dijkstra’s algorithm
d) Ford-Fulkerson algorithm
• Does Ford- Fulkerson algorithm use the idea
of?
a) Naïve greedy algorithm approach
b) Residual graphs
c) Minimum cut
d) Minimum spanning tree
• Under what condition can a vertex combine
and distribute flow in any manner?
a) It may violate edge capacities
b) It should maintain flow conservation
c) The vertex should be a source vertex
d) The vertex should be a sink vertex
• A simple acyclic path between source and
sink which pass through only positive
weighted edges is called?
a) augmenting path
b) critical path
c) residual path
d) maximum path
• In what time can an augmented path be
found?
a) O(|E| log |V|)
b) O(|E|)
c) O(|E|2)
d) O(|E|2 log |V|)
• What is the running time of an unweighted
shortest path algorithm whose augmenting
path is the path with the least number of
edges?
a) O(|E|)
b) O(|E||V|)
c) O(|E|2|V|)
d) O(|E| log |V|)