Chapter 41: DSA Edmonds-Karp Algorithm

DSA Edmonds-Karp Algorithm – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the network, writing numbers, showing every single flow change step by step, explaining why each decision is made, and most importantly helping you really feel the beauty of this algorithm.

What is the Edmonds-Karp Algorithm?

Edmonds-Karp is a specific implementation of the Ford-Fulkerson method for computing maximum flow in a flow network.

The most important difference from the general Ford-Fulkerson idea:

Edmonds-Karp always chooses the shortest possible augmenting path (in terms of number of edges) using BFS (Breadth-First Search).

This single change (using BFS instead of any path) turns the method from potentially exponential time into a guaranteed polynomial-time algorithm — O(V × E²).

That’s why almost every serious textbook, every competitive programming resource, and every interview question about maximum flow refers to Edmonds-Karp when they say “Ford-Fulkerson with BFS”.

Core Idea – Very Clear Intuition

The general Ford-Fulkerson says:

“Find any path from source to sink in the residual graph → send as much flow as possible along it → repeat until no path exists.”

But if you keep choosing bad paths (long, roundabout paths), you might need an enormous number of iterations.

Edmonds-Karp fixes this by saying:

“Always choose the shortest augmenting path (fewest edges) you can find — use BFS to guarantee this.”

This simple rule dramatically reduces the number of augmentations needed → makes the algorithm provably efficient.

Key Concepts You Must Understand First

Before we go to the example, make sure you are comfortable with these:

1. Residual graph — shows remaining forward capacity + backward capacity (undo option)
2. Augmenting path — path from source to sink in residual graph with positive residual capacity on every edge
3. Bottleneck — the smallest residual capacity along the augmenting path
4. Flow augmentation — increase flow along the path by the bottleneck value → decrease residual forward, increase residual backward (very important)

Classic Example – Step-by-step Execution (very detailed)

Flow network:

Vertices: s (source), A, B, C, t (sink)

Edges with capacities:

• s → A : 10
• s → B : 5
• A → B : 4
• A → C : 8
• B → C : 2
• B → t : 7
• C → t : 6

Initialize:

flow = 0 on all edges residual capacity = original capacity max_flow = 0

Iteration 1 Use BFS to find shortest augmenting path (shortest = fewest edges)

BFS layers:

• Level 0: s
• Level 1: A, B
• Level 2: C (from A), t (from B)

Shortest path found: s → B → t (2 edges)

Bottleneck = min(5, 7) = 5

Augment flow by 5:

• s → B: flow = 5, residual forward = 0, backward = 5
• B → t: flow = 5, residual forward = 2, backward = 5

max_flow = 5

Iteration 2 BFS again:

• Level 0: s
• Level 1: A (only, B has no forward residual)
• Level 2: B (from A), C (from A)
• Level 3: C (from B), t (from B)

Shortest path: s → A → B → t (3 edges)

Bottleneck = min(10, 4, 2) = 2

Augment by 2:

• s → A: flow = 2, residual forward = 8, backward = 2
• A → B: flow = 2, residual forward = 2, backward = 2
• B → t: flow = 7, residual forward = 0, backward = 7

max_flow = 7

Iteration 3 BFS:

• Level 0: s
• Level 1: A
• Level 2: B (from A), C (from A)
• Level 3: C (from B)

Path: s → A → C → t (3 edges)

Bottleneck = min(8, 8, 6) = 6

Augment by 6:

• s → A: flow = 8, residual forward = 2, backward = 8
• A → C: flow = 6, residual forward = 2, backward = 6
• C → t: flow = 6, residual forward = 0, backward = 6

max_flow = 13

Iteration 4 BFS — no path reaches t anymore (all paths blocked)

Maximum flow = 13

Final flow values:

• s → A : 8
• s → B : 5
• A → B : 2
• A → C : 6
• B → t : 7
• C → t : 6

Check: Out of s: 8 + 5 = 13 Into t: 7 + 6 = 13 → correct

Edmonds-Karp Code (standard interview version)

Why BFS Makes It Polynomial Time

The general Ford-Fulkerson can be exponential if you keep choosing bad (long) paths.

Edmonds-Karp proof insight (simplified):

• Each augmenting path is the shortest possible in terms of number of edges
• Each augmentation increases the shortest path length in residual graph
• There can be at most O(V) different possible shortest path lengths
• Number of augmentations ≤ O(V E) → total time O(V E²)

This guarantee is why Edmonds-Karp is preferred in teaching and interviews.

Summary – Edmonds-Karp in one line each

• BFS-based implementation of Ford-Fulkerson for maximum flow
• Always finds shortest augmenting path → polynomial time O(V E²)
• Uses residual graph + backward edges to allow canceling flow
• Handles any non-negative capacities
• One of the most important and most elegant flow algorithms
• Very frequently asked in interviews (often “implement max flow” means this)
• Foundation for many real-world problems: transportation, matching, bandwidth allocation, etc.

Would you like to go deeper into Edmonds-Karp or related maximum flow topics?

Very natural next steps:

• Complete step-by-step dry run of Edmonds-Karp on a graph with residual updates
• How to reconstruct the actual flow paths after algorithm finishes
• Ford-Fulkerson vs Edmonds-Karp – why BFS matters (with bad path example)
• Maximum bipartite matching using Edmonds-Karp (very common application)
• Min-cut – how to find the actual cut after max flow
• Dinic’s algorithm – faster alternative (very popular in competitive coding)

Just tell me which direction you want to go next — I’ll explain it in the same detailed, step-by-step, human-teacher style with clear examples and visuals! 😊