Algorithms
Ford-Fulkerson
Find max flow with Ford-Fulkerson.
Ford-Fulkerson
Ford-Fulkerson is a method for finding the maximum flow in a network. The core idea is to find augmenting paths and increase flow along them.
An augmenting path is a path from source to sink along which additional flow can be pushed. Each augmenting path increases the flow by its bottleneck value.
When no augmenting path remains, the maximum flow has been reached. Complexity depends on how paths are chosen.
Residual graph
The residual graph shows the remaining capacity and backward flow for each edge. For an edge (u,v) we have c_f(u,v) = c(u,v) - f(u,v).
When flow is reduced, a backward edge (v,u) appears; this allows flow to be pushed back. Augmenting paths are searched in this graph.
This structure gives Ford-Fulkerson the ability to both increase and retract flow.
Exercise ford_fulkerson function
Write ford_fulkerson(capacity, source, sink). capacity is an edge list (u, v, c); return the maximum flow. Print 5 with print(ford_fulkerson([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't')).
Show example solution
def ford_fulkerson(capacity, source, sink):
# Return the maximum flow
from collections import defaultdict
graph = defaultdict(dict)
for u, v, c in capacity:
graph[u][v] = graph[u].get(v, 0) + c
graph[v][u] = graph[v].get(u, 0)
max_flow = 0
def dfs(s, t, flow, visited):
if s == t:
return flow
visited.add(s)
for v in graph[s]:
if v not in visited and graph[s][v] > 0:
pushed = dfs(v, t, min(flow, graph[s][v]), visited)
if pushed > 0:
graph[s][v] -= pushed
graph[v][s] = graph[v].get(s, 0) + pushed
return pushed
return 0
while True:
visited = set()
f = dfs(source, sink, float('inf'), visited)
if f == 0:
break
max_flow += f
return max_flow
print(ford_fulkerson([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't'))
Test yourself
-
bottleneck flow
bottleneck = min(flow, capacity[u][____])
Show answer
bottleneck = min(flow, capacity[u][v])
-
When does Ford-Fulkerson stop?
while augmenting_path_exists():
push_flow()
- When the source is full
- When the sink is full
- When no augmenting path remains
- When all edges are full
Show answer
When no augmenting path remains — When no augmenting path remains, max flow is reached.
-
Ford-Fulkerson concepts
- augmenting path
- Push flow
- bottleneck
- Minimum residual capacity
- backward edge
- Retract flow
- maximum flow
- No augmenting path
Next lesson: Edmonds-Karp
