Ford-Fulkerson Algorithm in Flow Networks

Updated August 2026 — tutorial restored for this URL.

We are going to consider the Ford-Fulkerson method, which finds a maximum flow in a flow network. If you are new to the topic, read Introduction to Network Flow and Cuts in a Network first. A worked companion post is also here: The Ford-Fulkerson Algorithm.

We will cover:

What is a flow network?
What Ford-Fulkerson does
Residual graph and augmenting paths
Algorithm steps
Small example
Complexity and variants
Where to go next

1. What is a flow network?

A flow network is a directed graph where each edge has a non-negative capacity. We designate:

Source s — where flow starts
Sink t — where flow ends

A flow assigns a value to each edge such that:

0 ≤ flow(e) ≤ capacity(e)
For every vertex except s and t, inflow = outflow (conservation)

The value of the flow is the net amount leaving the source (equivalently, entering the sink).

2. What Ford-Fulkerson does

Ford-Fulkerson repeatedly finds a path from s to t that can still carry more flow (an augmenting path), pushes as much as possible along that path, and updates residual capacities — until no augmenting path remains. At that point the flow is maximum (max-flow min-cut theorem).

3. Residual graph and augmenting paths

The residual graph tracks leftover capacity:

Forward residual edge: capacity − current flow
Backward residual edge: current flow (lets you “undo” flow)

An augmenting path is any s→t path in the residual graph with positive residual capacity on every edge.

Bottleneck of a path = minimum residual capacity on that path. That is how much flow you can add in one augmentation.

4. Algorithm steps

Start with flow = 0 on every edge.
Build the residual graph.
While there exists an augmenting path p from s to t:
- Let b = bottleneck(p)
- For each forward edge on p: flow += b
- For each backward edge on p: flow −= b
- Update residual capacities
When no path remains, return the flow value.

Pseudocode:

Ford-Fulkerson(G, s, t):
    flow ← 0 for all edges
    while exists path p from s to t in residual(G):
        b ← min residual capacity on p
        augment flow along p by b
    return value(flow)

5. Small example (intuition)

Suppose s → a has capacity 10, a → t has capacity 6, and s → t has capacity 3.

First path s-a-t can push 6 (bottleneck at a-t). Flow value = 6.
Residual: s-a has 4 left; a-t is saturated.
Next path s-t can push 3. Flow value = 9.
No more augmenting path → maximum flow is 9.

Work the same idea on larger graphs by always searching the residual graph (DFS or BFS).

Python-style sketch (educational — not production-optimized):

from collections import defaultdict, deque

def edmonds_karp(capacity, s, t):
    # capacity[u][v] = residual capacity
    def bfs():
        parent = {s: None}
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap in capacity[u].items():
                if v not in parent and cap > 0:
                    parent[v] = u
                    if v == t:
                        return parent
                    q.append(v)
        return None

    flow_value = 0
    while True:
        parent = bfs()
        if not parent:
            break
        # bottleneck
        v = t
        b = float("inf")
        while v != s:
            u = parent[v]
            b = min(b, capacity[u][v])
            v = u
        # augment
        v = t
        while v != s:
            u = parent[v]
            capacity[u][v] -= b
            capacity[v][u] += b
            v = u
        flow_value += b
    return flow_value

Initialize capacity as a nested dict of edge capacities, and add reverse edges with 0 capacity before running.

6. Complexity and variants

Classic Ford-Fulkerson (DFS, arbitrary path choice) can be slow if capacities are large and path choice is unlucky.
Edmonds-Karp = Ford-Fulkerson using BFS for the shortest augmenting path → O(VE²).
Faster algorithms (Dinic, push-relabel) exist for competitive programming and large graphs.

7. Where to go next