An augmenting path is a route from a flow network’s source to its sink on which every edge has capacity available for additional flow. It matters when finding the maximum amount a network can carry, whether its edges represent pipes, data links, or roads. section 1.4.2
A path is not always augmenting
A → B → D is augmenting if both edges have remaining capacity. A → C → D is still a source-to-sink path, but it cannot carry more flow if C → D has no remaining capacity. section 1.4.2
Ford-Fulkerson uses augmenting paths to increase flow:
- Find a source-to-sink path with capacity available on every edge. Depth-first search is one option; the algorithm does not require a particular path-finding method. section 1.4.2
- Find the bottleneck: the smallest available capacity on that path. Send that much additional flow. section 1.4.2
- Update forward and backward capacities, then look for another augmenting path. Backward edges let later paths redistribute flow when an earlier path choice was suboptimal. section 1.4.2 section 1.5
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 pseudocode shows the stopping condition—no next augmenting path—and the paired update that decreases forward capacity while increasing backward capacity. section 1.4.2
Repeat until no augmenting path remains. At that point, Ford-Fulkerson returns the maximum flow. Do not mistake a blocked path for completion: another route may still have capacity. section 1.4.2 section 1.5
