01
Max-Flow: Ford-Fulkerson
Chapter 1 • Advanced
120 min
Max-Flow: Ford-Fulkerson
Problem Statement
Given a flow network with source s and sink t, find maximum flow from s to t.
Flow Network Properties
- Capacity constraint: f(u,v) ≤ c(u,v)
- Flow conservation: Σ f(u,v) = Σ f(v,w) for all v ≠ s,t
- Skew symmetry: f(u,v) = -f(v,u)
Ford-Fulkerson Algorithm
Algorithm Steps
- Initialize flow to 0
- While augmenting path exists:
- Find augmenting path (path with residual capacity > 0)
- Find minimum residual capacity on path
- Augment flow along path
- Return maximum flow
Implementation
python.js
from collections import deque
def ford_fulkerson(graph, source, sink):
"""
Ford-Fulkerson algorithm for max flow.
graph: adjacency matrix with capacities
Time: O(E * max_flow), Space: O(V)
"""
n = len(graph)
residual = [row[:] for row in graph]
max_flow = 0
while True:
# BFS to find augmenting path
parent = [-1] * n
queue = deque([source])
parent[source] = -2
while queue:
u = queue.popleft()
for v in range(n):
if parent[v] == -1 and residual[u][v] > 0:
parent[v] = u
queue.append(v)
if v == sink:
break
if parent[sink] == -1:
break # No augmenting path
# Find minimum residual capacity
path_flow = float('inf')
v = sink
while v != source:
u = parent[v]
path_flow = min(path_flow, residual[u][v])
v = u
# Augment flow
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
residual[u][v] -= path_flow
residual[v][u] += path_flow
v = u
return max_flow
Edmonds-Karp (BFS-based)
Uses BFS to find shortest augmenting path.
python.js
def edmonds_karp(graph, source, sink):
"""Edmonds-Karp: O(V * E²)"""
return ford_fulkerson(graph, source, sink) # Same implementation
Practice Problems
- Maximum flow in network
- Multiple sources/sinks
- Flow with lower bounds