T HE MA XIM U M
FL OW PR O BLEM
THE MAXIMUM FLOW ALGORITHM
The maximum flow problem involves determining the
most flow possible from a source vertex (s) to a sink
vertex (t) in a directed weighted graph.
Each edge in the graph has a capacity that limits the
amount of flow.
The objective is to maximize the flow without
exceeding the given capacities.
D -FU LK ERS ON
FOR TH M
A LG OR I
THE FORD-FULKERSON ALGORITHM
is a method to compute the maximum flow in a flow
network.
Key Idea: Repeatedly find augmenting paths from
source to sink and increase the flow along these paths
until no more augmenting paths exist.
This process continues until no more augmenting
paths exist.
KEY TERMS IN FORD-FULKERSON
Source (s): The starting vertex where the flow
originates.
Sink (t): Ending vertex.
Residual Graph: Adjusted graph showing remaining
capacities after considering current flow.
Augmenting Path: A path from source to sink in the
residual graph.
THE INTUITION BEHIND MAX FLOW
Imagine the edges as water
pipes, where the flow
represents the volume of
water allowed to pass through
each pipe.
The flow is limited by the
smallest capacity along the
path — often referred to as the
“bottleneck” value.
This bottleneck determines
the maximum amount of
water, or flow, that can travel
from the source to the sink,
considering all capacity
constraints in the network.
FINDING MAXIMUM FLOW WITH FORD-FULKERSON
With an infinite input source, how much "flow" can we
push through the network given that each edge has a
certain capacity?
EXAMPLE OF MAXIMUM FLOW CALCULATION
QUESTION: With an infinite input source, how much "flow" can we push
through the network given that each edge has a certain capacity?
In this flow graph, the maximum flow is 7, calculated as the sum of the
flows entering the sink node: 1 + 2 + 4 = 7. This value represents the
most flow that can be pushed through the network while respecting all
capacity limits.
FLOW GRAPH (FLOW NETWORK)
A flow graph (flow
network) is a directed
graph where each
edge (also called an
arc), has a certain
capacity which can
receive a certain
amount of flow. The
flow running through
an edge must be less
than or equal to the
capacity.
FLOW GRAPH (FLOW NETWORK)
FLOW GRAPH (FLOW NETWORK)
To find the maximum
flow (and the
minimum cut as a by-
product), the Ford-
Fulkerson method
repeatedly identifies
augmenting paths
through the residual
graph and increases
the flow along these
paths.
This process
continues until no
more augmenting
paths can be found.
AUGMENTING PATH
An augmenting path
is a path of edges in
the residual graph
with unused capacity
greater than zero
from the source s to
the sink t.
AUGMENTING PATH
In an augmenting path, the
bottleneck is the “smallest”
edge capacity along the path.
The flow can be augmented by
the bottleneck value, which is
the minimum remaining
capacity of all edges in the
path.
For example, given the
capacities along an
augmenting path:
(10-0, 15-0, 6-0, 25-0, 10-0),
the bottleneck value is
calculated as:
min(10, 15, 6, 25, 10) = 6
This means the flow can be
increased by 6 units along
this path.
AUGMENTING PATH
In an augmenting path, the
bottleneck is the “smallest”
edge capacity along the path.
The flow can be augmented by
the bottleneck value, which is
the minimum remaining
capacity of all edges in the
path.
For example, given the
capacities along an
augmenting path:
(10-0, 15-0, 6-0, 25-0, 10-0),
the bottleneck value is
calculated as:
min(10, 15, 6, 25, 10) = 6
This means the flow can be
increased by 6 units along
this path.
AUGMENTING PATH
In an augmenting path, the
bottleneck is the “smallest”
edge capacity along the path.
The flow can be augmented by
the bottleneck value, which is
the minimum remaining
capacity of all edges in the
path.
For example, given the
capacities along an
augmenting path:
(10-0, 15-0, 6-0, 25-0, 10-0),
the bottleneck value is
calculated as:
min(10, 15, 6, 25, 10) = 6
This means the flow can be
increased by 6 units along
this path.
AUGMENTING PATH
Augmenting the flow
means updating the
flow
values of the edges
along the augmenting
path.
For forward edges, this
means increasing
the flow by the
bottleneck value.
AUGMENTING PATH
Augmenting the flow
means updating the
flow values of the
edges along the
augmenting path.
For forward edges, this
means increasing the
flow by the bottleneck
value.
AUGMENTING PATH
Augmenting the flow
means updating the
flow values of the
edges along the
augmenting path.
For forward edges, this
means increasing the
flow by the bottleneck
value.
RESIDUAL EDGES
When augmenting the
flow along the
augmenting
path, you also need to
decrease the flow
along each residual
edge by the bottleneck
value.
RESIDUAL EDGES
Residual edges exist to
“undo” bad augmenting
paths which do not
lead to a maximum
flow.
RESIDUAL GRAPH
Imagine that every
edge in the original
graph has an
associated residual
edge—which is
typically not displayed
—that starts with a
flow and capacity of
0/0.
The residual graph is
simply the original
graph augmented with
these residual edges.
In general, when I
refer to the "flow
graph," it means the
residual graph.
RESIDUAL GRAPH
Q: Residual edges have a capacity of
0? Isn't that forbidden? How does
that work?
Think of the remaining capacity of an edge e -
whether residual or not as:
e.capacity e.flow
This formula ensures that the
remaining capacity of an edge is
always non-negative, even if the
flow can be adjusted in the reverse
direction (which may appear as
"negative" flow in the context of
residual graphs).
RESIDUAL GRAPH
The bottleneck is 4
because it is the
minimum of the
remaining capacities
along the augmenting
path:
min(10 – 6, 15 − 6, 10 −
0) = min(4, 9, 10) = 4
This means the
maximum additional
flow that can be
pushed through this
path is limited by the
smallest available
capacity, which is 4.
RESIDUAL GRAPH
The bottleneck value is
6 because it is the
smallest remaining
capacity among the
edges of the
augmenting path:
min(10 – 0, 0 − −6, 10 −
4) = min(10, 6, 6) = 6
This means the
maximum additional
flow that can be
pushed through this
path is limited by the
smallest available
capacity, which is 6.
RESIDUAL GRAPH
Augment edges with
bottleneck value of 6
RESIDUAL GRAPH
Augment edges with
bottleneck value of 6
RESIDUAL GRAPH
The bottleneck value is
4 since the smallest
remaining capacity
amongst the edges of
our
augmenting path is:
min(10 – 6, 25 – 6, 10 −
6) = min(4, 19,
RESIDUAL GRAPH
Augment edges with
bottleneck value of 4
RESIDUAL GRAPH
No more augmenting
paths can be found,
so the algorithm
terminates!
maximum flow = 6 + 4 + 6 + 4 = 20
bottleneck values
RESIDUAL GRAPH
The time complexity of
the Ford-Fulkerson
method depends on the
algorithm being used
to find the augmenting
paths, which is left
unspecified.
RESIDUAL GRAPH
Assuming the
method of finding
augmenting
paths is by using a
Depth First Search
(DFS),
the algorithm runs
in 0(fE), where f is
the
maximum flow and E
is the number of
edges.
RESIDUAL GRAPH
Recall that a DFS
traversal chooses
edges in
a random order, so it
is possible to pick
the
middle edge every
time when finding
an augmenting path.
RESIDUAL GRAPH
This results in
flipping back and
forth
between the same
two alternating
paths
for 200 iterations...
RESIDUAL GRAPH
RESIDUAL GRAPH
NOTE: Be mindful that the time complexities
for flow algorithms are very pessimistic. In
practice, they tend to operate much faster,
making it hard to compare the performance of
flow algorithms solely based on complexity.
