Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm finds the maximum flow in a network by augmenting paths in the residual graph.

Implementations

code.py
1def ford_fulkerson(graph, source, sink):
2    # Initialize the residual graph
3    residual_graph = defaultdict(dict)
4    
5    for u, v, capacity in graph:
6        residual_graph[u][v] = capacity
7    
8    # Initialize the flow
9    flow = 0  
10    
11    while True:
12        # Find an augmenting path
13        path = shortestPath(residual_graph, source, sink)
14        
15        if not path:
16            break 
17        
18        # Update the flow
19        flow += min(residual_graph[u][v] for u, v in path)
20        
21        # Update the residual graph
22        for u, v in path:
23            residual_graph[u][v] -= flow  
24    
25    return flow # The maximum flow
26
27def shortestPath(graph, source, sink):
28    # Initialize the queue
29    queue = deque([source])
30    
31    # Initialize the parent dictionary
32    parent = {} # parent[node] = previous node in the path
33    
34    while queue:
35        u = queue.popleft()
36        
37        for v in graph[u]:
38            if v not in parent:
39                parent[v] = u # Set the parent of v to u
40                queue.append(v) # Add v to the queue
41    
42    return parent # The path from source to sink in the residual graph