Maximum Flow (Ford-Fulkerson)

DSA · Graphs

Theory

The maximum flow problem asks how much can be sent from a source to a sink through a network where each edge has a capacity, like water through pipes or data through network links. Ford-Fulkerson solves it by repeatedly finding an augmenting path, a path from source to sink that still has spare capacity, and pushing as much flow as the smallest capacity on that path allows. It keeps a residual graph: after sending flow along an edge, it reduces that edge's remaining capacity and adds a reverse edge so that later paths can undo earlier choices. When no augmenting path remains, the total flow is maximal. The max-flow min-cut theorem says this value equals the capacity of the smallest cut separating source and sink.

Why we use it

Many allocation problems reduce to max flow: matching applicants to jobs, routing traffic, scheduling, and finding bottlenecks in pipelines or supply chains.

When to use it

Use it when you need the most of something that can pass through a capacitated network, or the minimum set of edges whose removal disconnects source and sink.

How it works

  1. flow = 0, residual = capacities
  2. Augmenting path s -> t exists? Yes: b = smallest residual on path. No: Stop: flow is maximum.
  3. Push b: forward -= b, reverse += b
  4. flow = flow + b, repeat

Syntax

while augmenting path p exists in residual graph:
    f = min residual capacity on p
    push f along p (update forward and reverse edges)
DFS version: O(E * max_flow)

Example

def max_flow(cap, s, t):
    n = len(cap)
    flow = 0
    residual = [row[:] for row in cap]

    def dfs(u, pushed, seen):
        if u == t:
            return pushed
        seen.add(u)
        for v in range(n):
            if v not in seen and residual[u][v] > 0:
                got = dfs(v, min(pushed, residual[u][v]), seen)
                if got:
                    residual[u][v] -= got
                    residual[v][u] += got
                    return got
        return 0

    while True:
        pushed = dfs(s, float("inf"), set())
        if not pushed:
            return flow
        flow += pushed

# 0 = source, 5 = sink
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],
]
print("Maximum flow:", max_flow(cap, 0, 5))

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