12.3 Ford-Fulkerson Algorithm

Problem

Given a flow network with capacities on every edge, determine the maximum amount of flow that can be sent from the source to the sink.

For small networks, it is often possible to find a solution manually. For larger networks, the number of possible flow assignments becomes enormous. Exhaustively searching all assignments quickly becomes impractical.

We need a systematic method that starts from an empty flow and gradually improves it until no further improvement is possible.

Solution

The Ford-Fulkerson method repeatedly finds an augmenting path in the residual graph and pushes as much flow as possible through that path.

The algorithm follows a remarkably simple strategy:

Start with zero flow.
Build the residual graph.
Find a source-to-sink path.
Compute the bottleneck capacity.
Push flow through the path.
Update the residual graph.
Repeat until no augmenting path exists.

The final flow is maximum.

Core Idea

Suppose we have:

S → A → T

with capacities:

Edge	Capacity
S → A	10
A → T	8

The largest flow that can travel through the path is:

min(10, 8) = 8

The smallest capacity along the path determines how much additional flow can be added.

This value is called the bottleneck capacity.

First Example

Consider:

        10
    S ------> A
    |         |
 10 |         | 8
    v         v
    B ------> T
        10

Capacities:

Edge	Capacity
S → A	10
S → B	10
A → T	8
B → T	10

Iteration 1

Find path:

S → A → T

Bottleneck:

min(10, 8) = 8

Push:

units.

Current flow:

Edge	Flow
S → A	8
A → T	8

Total flow:

Iteration 2

Residual graph still contains:

S → B → T

Bottleneck:

min(10, 10) = 10

Push:

units.

Total flow becomes:

Iteration 3

No augmenting path remains.

Algorithm terminates.

Maximum flow:

Why It Works

Suppose an augmenting path exists.

Then additional flow can reach the sink.

Therefore the current flow cannot be optimal.

Conversely, if no augmenting path exists, the residual graph separates the source from the sink.

At that point a minimum cut has been reached.

The max-flow min-cut theorem guarantees optimality.

This theorem will be proven later in the chapter.

Algorithm

Initialize:

flow = 0

Repeat:

Find augmenting path in residual graph.
If none exists, stop.
Compute bottleneck capacity.
Augment flow.
Update residual graph.

Return:

flow

Pseudocode

FordFulkerson(G, s, t):

    maxFlow = 0

    while augmenting path P exists:

        bottleneck = minimum residual capacity on P

        augment P by bottleneck

        maxFlow += bottleneck

    return maxFlow

The simplicity of the algorithm is one reason it remains one of the most important ideas in graph optimization.

Detailed Example

Consider:

          10
     S ------> A
     |         |
  10 |         | 4
     v         v
     B ------> T
          10

Additional edge:

A → B = 6

First Augmentation

Choose:

S → A → B → T

Bottleneck:

min(10, 6, 10) = 6

Flow becomes:

Edge	Flow
S → A	6
A → B	6
B → T	6

Total:

Residual Network

Reverse edge appears:

B → A

with residual capacity:

Second Augmentation

Choose:

S → B → A → T

This path contains:

B → A

which is a reverse edge.

Bottleneck:

Pushing 4 units:

adds flow to S → B
removes 4 units from A → B
adds 4 units to A → T

New flows:

Edge	Flow
S → A	6
S → B	4
A → B	2
A → T	4
B → T	6

Total flow:

Notice that the algorithm improved the solution by partially undoing an earlier decision.

This is exactly why residual graphs are necessary.

Finding Augmenting Paths

Ford-Fulkerson itself does not specify how paths are found.

Possible approaches:

Method	Search
DFS	Depth-first search
BFS	Breadth-first search
Heuristic	Custom search

Different choices lead to different performance characteristics.

The famous Edmonds-Karp algorithm is simply Ford-Fulkerson using BFS.

Complexity Analysis

Let:

(V) = number of vertices
(E) = number of edges
(F) = maximum flow value

If augmenting paths are found using DFS:

Operation	Cost
One search	O(E)
Number of augmentations	O(F)
Total	O(EF)

Thus:

O(EF)

for integer capacities.

This is often acceptable for small and medium networks.

For large capacities it may become slow.

Limitation with Real Numbers

Ford-Fulkerson assumes augmentations eventually terminate.

With irrational capacities, unfortunate path choices can produce infinitely many augmentations.

The flow converges toward the optimum but never reaches it exactly.

This issue motivated later algorithms such as Edmonds-Karp and Dinic, which guarantee termination.

For integer capacities, Ford-Fulkerson always terminates because every augmentation increases flow by at least one unit.

Implementation Pattern

Most implementations store:

Edge {
    to
    residual_capacity
    reverse_edge
}

DFS searches the residual graph:

dfs(u):

    if u == sink:
        return flow

    for residual edge:

        if capacity > 0:

            recurse

After discovering a path:

forward -= pushed
reverse += pushed

This update automatically maintains residual capacities.

Correctness Sketch

At every step:

Flow remains feasible.
Capacity constraints remain satisfied.
Conservation remains satisfied.

Each augmentation strictly increases total flow.

When no augmenting path exists:

source and sink become disconnected in the residual graph
a cut separates them
flow equals cut capacity

Therefore the flow is maximum.

Common Mistakes

Searching Original Edges

The search must operate on residual edges.

Ignoring reverse edges can produce incorrect results.

Forgetting Bottlenecks

The amount pushed equals:

minimum residual capacity on path

not the maximum.

Incorrect Residual Updates

Both directions must be updated:

forward -= pushed
reverse += pushed

every time.

Ignoring Integer Overflow

Large capacities may exceed 32-bit integer limits.

Use 64-bit integers when capacities can be large.

Takeaway

Ford-Fulkerson is the foundational maximum-flow algorithm. Starting from zero flow, it repeatedly discovers augmenting paths in the residual graph and increases flow until no such path remains.

Its importance extends far beyond its practical performance. Nearly every modern flow algorithm, including Edmonds-Karp, Dinic, push-relabel methods, and many specialized network optimization techniques, builds upon the central Ford-Fulkerson idea:

If a path exists in the residual graph, the current flow can still be improved.

The next recipe refines this approach by choosing augmenting paths with breadth-first search, leading to the Edmonds-Karp algorithm and its polynomial-time guarantee.