Ford-Fulkerson
- Algorithms course
- Expert
- Lesson 26/41
- 4 min
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.
Practice 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')).
Starter code
def ford_fulkerson(capacity, source, sink):
# Return the maximum flowSample 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'))Expected output
5
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 bottleneck flow
bottleneck = min(flow, capacity[u][____])bottleneck = min(flow, capacity[u][v])Explanation: capacity[u][v] gives the bottleneck.
2 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 Correct answer
- When all edges are full
Explanation: When no augmenting path remains, max flow is reached.
3 Ford-Fulkerson concepts
| Term | Meaning |
|---|---|
augmenting path |
Push flow |
bottleneck |
Minimum residual capacity |
backward edge |
Retract flow |
maximum flow |
No augmenting path |