The Ford-Fulkerson algorithm finds the maximum flow that can travel through a network from a source to a sink without exceeding any connection’s capacity. Think of water moving through pipes, packets through network links, or cars along roads: the question is how much can reach the destination at once. section 1.4.2
A flow network has vertices connected by directed edges. Each edge has a capacity—the most it can carry—and a flow—the amount currently passing through it. The source is where flow starts; the sink is where it ends. section 1.4.2
Ford-Fulkerson increases the flow one augmenting path at a time:
- Find a path from source to sink whose edges all have room for more flow. If none exists, return the accumulated flow. section 1.4.2
- Find the path’s bottleneck, then reduce the available capacity of each edge on the path by that amount. section 1.4.2
- Increase the corresponding backward-edge capacities. These allow later paths to redistribute flow if an earlier path choice was suboptimal. section 1.4.2 section 1.5
A path is not necessarily usable
A → B → D is an augmenting path when both edges have remaining capacity. A → C → D may still connect the source to the sink, but it cannot carry additional flow if C → D has no capacity left. section 1.4.2
def ford_fulkerson(graph, source, sink):
res = 0
while True:
path = get_next_augmenting_path(graph, source, sink)
if path is None:
break
bottleneck = get_bottleneck(path)
for edge in path.get_edges():
edge.capacity -= bottleneck
backward_edge = get_backward_edge(graph, edge)
backward_edge.capacity += bottleneck
res += bottleneck
return res
The Python sketch shows the repeat-and-update loop. It leaves path finding, bottleneck calculation, and backward-edge lookup to helper functions. section 1.4.2
