DSA Graphs

Ford-Fulkerson Method

Scene: every rush-hour you find one more open corridor and push cars until a street saturates. Ford-Fulkerson is that loop formalized: find a residual s–t path, push the , repeat.

It is a , not one DFS. and the path rule control .

Algorithm journey

Start at zero flow

Residuals = capacities.

Find residual s–t path

Any positive-capacity walk.

Saturate at least one edge.

Stop when no path

Min-cut certificate via residual reachability.

What actually happens

Naive idea: pack edge-disjoint paths without reverse residual edges. Breaks when the true optimum needs to cancel earlier flow.

Better idea: treat reverse residual capacity as first-class. Each augmentation preserves a feasible flow and raises value by Δ≥1 on integer networks.

The improved design still fails with adversarial path choice on huge |f*| (too many augmentations) or irrational capacities (possible non-termination).

Invariant

After every augmentation the flow is feasible. When no residual s–t path remains, residual reachability from s yields a cut whose capacity equals the flow value.

How to choose Ford-Fulkerson

1. Teaching residuals? Start here.

2. Need a poly bound? Specialize to Edmonds-Karp (BFS).

3. Large sparse nets? Prefer Dinic or push-relabel.

Quantitative check

Integer DFS Ford-Fulkerson can take Θ(E · |f*|) augmentations. If |f*|=10⁶ and each BFS/DFS is costly, the method becomes unusable even when V is small.

Interactive demo

Iteration: 0

Max Flow: 0

Click Play to find augmenting paths!

0SRC

5SINK

Source

Sink

Current Flow

Augmenting Path

flow/capacity (res: residual)

The invariant behind every augmentation

Find

Search only residual edges with positive capacity. Any such s–t path is legal.

Bottleneck

Let Δ be the minimum residual capacity on the path. At least one edge becomes saturated.

Undo safely

Subtract Δ forward and add it to the paired reverse edge. Feasibility and conservation remain true.

If no augmenting path exists, residual reachability from the source produces a cut whose capacity equals the current flow. That is both the stopping proof and a machine-checkable optimality certificate.

Path choice controls termination

Capacities / rule	Guarantee	What to remember
Integer + arbitrary DFS	O(E · \|f*\|)	Each augmentation raises total flow by at least 1; pseudo-polynomial in the numeric value.
Rational capacities	Terminates after scaling	The common denominator can be huge, so this still gives no strong polynomial bound.
Irrational capacities	May not terminate	A pathological path sequence can converge forever, even to a value below the maximum.
BFS shortest paths	O(VE²)	This specialization is Edmonds-Karp; its bound is independent of capacity magnitudes.

📝 Algorithm Steps

Initialize Flow

Start with zero flow on all edges. Create a residual graph with the same capacities as the original graph.

Find Augmenting Path

Search for a path from source to sink in the residual graph using DFS or BFS. If no path exists, we're done!

Find Bottleneck

Determine the minimum residual capacity along the augmenting path. This is the maximum flow we can push through this path.

Update Residual Graph

Increase flow along the path by the bottleneck value. Update residual capacities: decrease forward edges, increase backward edges.

Repeat

Go back to step 2 and repeat until no augmenting path can be found.

🔍 Did You Know? Residual Graphs Enable Flow Reversal

The genius of Ford-Fulkerson is the residual graph with backward edges! When you send flow along an edge (u → v), you create a backward edge (v → u) with capacity equal to the flow. This allows the algorithm to "undo" previous decisions if a better path is found later. It's like having an undo button for flow routing!

💻 DFS Ford-Fulkerson: safe edge-list implementation

Python

python

class Edge:
    def __init__(self, to: int, rev: int, residual: int) -> None:
        self.to = to
        self.rev = rev
        self.residual = residual

class FordFulkerson:
    """DFS path selection; intended for non-negative integer capacities."""
    def __init__(self, n: int) -> None:
        if n <= 0:
            raise ValueError("n must be positive")
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, capacity: int) -> None:
        if not (0 <= u < len(self.graph) and 0 <= v < len(self.graph)):
            raise IndexError("vertex out of range")
        if u == v:
            raise ValueError("self-loops are not supported")
        if capacity < 0:
            raise ValueError("capacity must be non-negative")
        forward = Edge(v, len(self.graph[v]), capacity)
        reverse = Edge(u, len(self.graph[u]), 0)
        self.graph[u].append(forward)
        self.graph[v].append(reverse)

    def _dfs(self, u: int, sink: int, pushed: int, seen: list[bool]) -> int:
        if u == sink:
            return pushed
        seen[u] = True
        for edge in self.graph[u]:
            if edge.residual == 0 or seen[edge.to]:
                continue
            sent = self._dfs(edge.to, sink, min(pushed, edge.residual), seen)
            if sent:
                edge.residual -= sent
                self.graph[edge.to][edge.rev].residual += sent
                return sent
        return 0

    def max_flow(self, source: int, sink: int) -> int:
        if not (0 <= source < len(self.graph) and 0 <= sink < len(self.graph)):
            raise IndexError("vertex out of range")
        if source == sink:
            raise ValueError("source and sink must differ")
        total = 0
        while True:
            source_bound = sum(edge.residual for edge in self.graph[source])
            if source_bound == 0:
                return total
            sent = self._dfs(source, sink, source_bound, [False] * len(self.graph))
            if sent == 0:
                return total
            total += sent

flow = FordFulkerson(6)
for u, v, capacity in [
    (0, 1, 16), (0, 2, 13), (1, 2, 10), (2, 1, 4),
    (1, 3, 12), (2, 4, 14), (3, 2, 9), (4, 3, 7),
    (3, 5, 20), (4, 5, 4),
]:
    flow.add_edge(u, v, capacity)

assert flow.max_flow(0, 5) == 23

Java

java

import java.util.ArrayList;
import java.util.List;

public class FordFulkerson {
    static final class Edge {
        final int to;
        final int rev;
        long residual;
        Edge(int to, int rev, long residual) {
            this.to = to; this.rev = rev; this.residual = residual;
        }
    }

    private final List<List<Edge>> graph;

    FordFulkerson(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    }

    void addEdge(int u, int v, long capacity) {
        if (u < 0 || u >= graph.size() || v < 0 || v >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (u == v) throw new IllegalArgumentException("self-loop");
        if (capacity < 0) throw new IllegalArgumentException("negative capacity");
        Edge forward = new Edge(v, graph.get(v).size(), capacity);
        Edge reverse = new Edge(u, graph.get(u).size(), 0L);
        graph.get(u).add(forward);
        graph.get(v).add(reverse);
    }

    private long dfs(int u, int sink, long pushed, boolean[] seen) {
        if (u == sink) return pushed;
        seen[u] = true;
        for (Edge edge : graph.get(u)) {
            if (edge.residual == 0 || seen[edge.to]) continue;
            long sent = dfs(edge.to, sink, Math.min(pushed, edge.residual), seen);
            if (sent != 0) {
                edge.residual -= sent;
                graph.get(edge.to).get(edge.rev).residual += sent;
                return sent;
            }
        }
        return 0L;
    }

    long maxFlow(int source, int sink) {
        if (source < 0 || source >= graph.size() || sink < 0 || sink >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (source == sink) throw new IllegalArgumentException("source == sink");
        long total = 0L;
        while (true) {
            long sent = dfs(source, sink, Long.MAX_VALUE, new boolean[graph.size()]);
            if (sent == 0) return total;
            total = Math.addExact(total, sent);
        }
    }

    public static void main(String[] args) {
        FordFulkerson flow = new FordFulkerson(6);
        long[][] edges = {
            {0,1,16}, {0,2,13}, {1,2,10}, {2,1,4}, {1,3,12},
            {2,4,14}, {3,2,9}, {4,3,7}, {3,5,20}, {4,5,4}
        };
        for (long[] edge : edges) flow.addEdge((int) edge[0], (int) edge[1], edge[2]);
        if (flow.maxFlow(0, 5) != 23L) throw new AssertionError();
    }
}

🎯 Key Insight: Method vs Algorithm

Ford-Fulkerson is a method, not a specific algorithm! The time complexity depends on HOW you find augmenting paths:

• DFS: Can be slow, O(E × f) where f is max flow
• BFS (Edmonds-Karp): Polynomial time, O(V E²)
• Shortest augmenting path: Better performance

⚡ Complexity Analysis

Time Complexity

•
O(E · |f*|) with DFS and integral capacities
Pseudo-polynomial: |f*| can be exponential in the input bit length.
•
O(V E²) with BFS
Polynomial time (Edmonds-Karp)
•
Worst case: Exponential with poor path choices
Can alternate between bad paths

Space Complexity

•
O(V + E)
Paired residual adjacency lists plus DFS state.
•
O(V) auxiliary
Visited state and a DFS stack up to V vertices

💡 Choose the path rule deliberately

DFS is acceptable for tiny integral instances and demonstrates the method, while BFS gives Edmonds-Karp's predictable polynomial bound. For performance-sensitive sparse graphs, jump to Dinic rather than assuming BFS is always the fastest. Recursive DFS can also overflow the call stack on a long chain; use an iterative search or increase care around recursion limits.

Engineering checklist

• Reject negative capacities, self-loops, and source == sink.
• Use paired reverse indices for parallel and antiparallel edges.
• Use Python integers or Java long; check total-flow overflow.
• A disconnected sink correctly returns 0.
• Test one edge, no path, parallel edges, cycles, and a path requiring cancellation.
• Treat the residual object as one-shot; rebuild it before another query.
• Validate capacity, conservation, and min-cut equality after the run.

✅ Pros & ❌ Cons

✅ Advantages

✓Simple and intuitive concept
✓Foundation for many max flow algorithms
✓Flexible - works with any path-finding method
✓Easy to implement and understand

❌ Limitations

✗Can be very slow with poor path choices (DFS)
✗May not terminate with irrational capacities
✗Time depends on max flow value (not polynomial with DFS)
✗Slower than modern algorithms (Dinic's, Push-Relabel)

💼 Real World Application: Network Reliability

Internet service providers use Ford-Fulkerson-based algorithms to determine network reliability. By modeling routers as nodes and connections as edges with bandwidth capacities, they can calculate the maximum data throughput between data centers. This helps identify bottlenecks and plan network upgrades!

Short takeaway

Ford-Fulkerson repeatedly augments along residual paths. Correct residuals (including reverse edges) matter as much as the search rule; path choice controls termination and speed.

Exercises

Show an integer network where a bad DFS order causes |f*| augmentations of size 1. What changes if you switch to BFS?
After one augmentation, write the residual capacities including reverse. Which new path becomes legal?
Why is Ford-Fulkerson a method rather than a single algorithm?

Primary sources

Ford, L. R. & Fulkerson, D. R.: Maximal flow through a network.
Cormen et al., CLRS: The Ford-Fulkerson method.
Edmonds & Karp (1972): for the BFS specialization and poly bound.