Edmonds-Karp

DSA · Graphs

Theory

Edmonds-Karp is Ford-Fulkerson with one rule: always choose the shortest augmenting path, found with breadth-first search. That small change guarantees a polynomial running time of O(V * E^2), no matter how large the capacities are, while plain DFS-based Ford-Fulkerson can take time proportional to the flow value itself. Each BFS finds the path with the fewest edges in the residual graph, the bottleneck capacity along it is pushed, and the residual capacities are updated in both directions. The algorithm stops when BFS can no longer reach the sink. Recording the parent of each vertex during BFS lets you walk the path back from sink to source.

Why we use it

It gives predictable performance for max-flow problems and is the version most textbooks and interviewers expect you to implement.

When to use it

Use it for max-flow and bipartite matching on small to medium graphs. For very large networks, faster algorithms such as Dinic's are used.

How it works

  1. flow = 0
  2. BFS for the shortest path s -> t in residual graph
  3. Path found? Yes: Bottleneck b, update residuals, flow += b. No: Stop: maximum flow.
  4. Repeat BFS

Syntax

while BFS finds path s -> t in residual graph:
    bottleneck = min capacity on path
    update residual (forward -= b, backward += b)
Time O(V * E^2)

Example

from collections import deque

def edmonds_karp(cap, s, t):
    n = len(cap)
    residual = [row[:] for row in cap]
    flow, paths = 0, []
    while True:
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q and parent[t] == -1:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u
                    q.append(v)
        if parent[t] == -1:
            return flow, paths
        path, v, b = [t], t, float("inf")
        while v != s:
            b = min(b, residual[parent[v]][v])
            v = parent[v]
            path.append(v)
        v = t
        while v != s:
            residual[parent[v]][v] -= b
            residual[v][parent[v]] += b
            v = parent[v]
        flow += b
        paths.append((path[::-1], b))

cap = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0],
]
total, paths = edmonds_karp(cap, 0, 5)
for p, b in paths:
    print("path", p, "pushes", b)
print("Maximum flow:", total)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic