12.4 Edmonds-Karp Algorithm

Problem

The Ford-Fulkerson method provides a simple framework for computing maximum flow, but its performance depends heavily on the choice of augmenting paths.

Different path selections can lead to dramatically different running times.

Consider a network where one path increases flow by 100 units while another increases flow by only 1 unit. A poor path selection strategy may require thousands of augmentations before reaching the optimum.

Even worse, Ford-Fulkerson lacks a polynomial-time guarantee for arbitrary capacities.

We need a path selection strategy that produces predictable performance and a provable complexity bound.

Solution

Edmonds-Karp is Ford-Fulkerson with one additional rule:

Always choose the shortest augmenting path in the residual graph.

Shortest means the path containing the fewest edges.

The algorithm finds these paths using Breadth-First Search (BFS).

This simple modification leads to a polynomial-time algorithm with complexity:

O(VE²)

where:

(V) = vertices
(E) = edges

Core Insight

Ford-Fulkerson allows any augmenting path.

Edmonds-Karp always chooses:

Source
   ↓
Fewest edges
   ↓
Sink

This restriction creates a useful structural property.

As the algorithm progresses, distances from the source to vertices in the residual graph never decrease.

This monotonic behavior prevents pathological cases.

Example Network

Consider:

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

Additional edge:

A → B = 6

Capacities:

Edge	Capacity
S → A	10
S → B	10
A → B	6
A → T	4
B → T	10

Iteration 1

Run BFS.

Shortest path:

S → A → T

Length:

2 edges

Bottleneck:

min(10,4)=4

Push:

Flow value:

Iteration 2

Residual graph still contains:

S → B → T

BFS discovers:

S → B → T

Bottleneck:

Push:

Flow value:

Iteration 3

BFS now finds:

S → A → B → T

Bottleneck:

Push:

Total flow:

No augmenting path remains.

Maximum flow equals:

Why BFS Matters

Suppose DFS is used.

The search may repeatedly choose long inefficient paths.

Example:

S → A → C → D → E → T

even when:

S → B → T

exists.

The algorithm still reaches the optimum but may perform many unnecessary augmentations.

BFS always prioritizes the shortest residual path.

This choice yields stronger theoretical guarantees.

Distance Labels

During BFS every vertex receives a distance from the source.

Example:

S
├── A
└── B
     └── T

Distances:

Vertex	Distance
S	0
A	1
B	1
T	2

Edmonds-Karp always augments along paths consistent with these shortest distances.

A crucial theorem states:

Residual distances never decrease during the algorithm.

This observation drives the complexity proof.

Algorithm

Initialize:

flow = 0

Repeat:

Run BFS on residual graph.
Find shortest augmenting path.
If no path exists, stop.
Compute bottleneck capacity.
Augment flow.
Update residual graph.

Return:

maximum flow

Pseudocode

EdmondsKarp(G,s,t):

    maxFlow = 0

    while BFS finds path P:

        bottleneck =
            minimum residual capacity on P

        augment P

        maxFlow += bottleneck

    return maxFlow

The structure remains identical to Ford-Fulkerson.

Only path selection changes.

BFS Implementation

Store:

parent[v]

for each discovered vertex.

Example:

parent[A] = S
parent[T] = A

Once BFS reaches the sink:

T ← A ← S

reconstructs the augmenting path.

Typical BFS:

queue ← source

while queue not empty:

    remove vertex

    explore residual edges

    if sink reached:
        stop

Residual Updates

Suppose:

A → B

has residual capacity:

and bottleneck:

Update:

forward  = 8 - 3
reverse  = reverse + 3

This operation remains identical to Ford-Fulkerson.

Correctness

The correctness argument follows directly from Ford-Fulkerson.

Each augmentation:

preserves feasibility
respects capacities
preserves conservation

When BFS cannot reach the sink:

No augmenting path exists

Therefore the current flow is maximum.

The max-flow min-cut theorem guarantees optimality.

Complexity Analysis

Single BFS

Using adjacency lists:

O(E)

Number of Augmentations

The key Edmonds-Karp theorem states:

Each edge becomes critical at most:

O(V)

times.

There are:

edges.

Therefore:

O(VE)

augmentations.

Total

Combining both:

O(E) × O(VE)
=
O(VE²)

This bound is independent of flow values.

Unlike Ford-Fulkerson:

O(EF)

the running time no longer depends on maximum flow magnitude.

Example of Improvement

Suppose:

Maximum Flow = 1,000,000

Ford-Fulkerson with unlucky path choices may require:

1,000,000

augmentations.

Edmonds-Karp depends only on graph size.

Large capacities no longer cause performance disasters.

Practical Performance

Edmonds-Karp works well for:

Small networks
Medium networks
Educational implementations
Interview problems

Performance becomes inadequate for:

Dense graphs
Very large networks
Competitive programming flow-heavy tasks

In those cases Dinic's algorithm is usually preferred.

Common Mistakes

Using DFS Instead of BFS

A DFS implementation is Ford-Fulkerson, not Edmonds-Karp.

The polynomial complexity guarantee disappears.

Forgetting Parent Tracking

BFS must reconstruct the path.

Without parent information augmentation cannot occur.

Searching Saturated Edges

Only residual edges with positive capacity should be traversed.

Incorrect Early Exit

Once BFS reaches the sink, the shortest augmenting path has already been found.

Continuing the search wastes work.

Comparison with Ford-Fulkerson

Feature	Ford-Fulkerson	Edmonds-Karp
Path selection	Arbitrary	BFS shortest path
Complexity	O(EF)	O(VE²)
Depends on flow value	Yes	No
Polynomial guarantee	Not always	Yes
Implementation difficulty	Easy	Easy
Practical speed	Moderate	Moderate

Edmonds-Karp provides the first fully polynomial maximum-flow algorithm while retaining the conceptual simplicity of Ford-Fulkerson.

Takeaway

Edmonds-Karp transforms Ford-Fulkerson into a polynomial-time algorithm by always selecting the shortest augmenting path in the residual graph using BFS.

The key contribution is not a new flow model or a new residual structure. The innovation lies entirely in path selection. This seemingly small change produces strong theoretical guarantees and establishes many of the ideas later used by faster algorithms.

The next recipe introduces Dinic's algorithm, which extends the shortest-path concept further by constructing level graphs and sending flow through many shortest paths simultaneously, reducing the running time dramatically on large networks.