Maximum flow is the greatest amount that can travel through a flow network from a source to a sink without exceeding any edge’s capacity. A vertex is a point where flow enters or exits; a directed edge carries flow and has a capacity limit. The source is where flow starts, and the sink is where it is collected. section 1.4.2
A path is not always usable
Suppose A is the source and D is the sink. A → B → D is an augmenting path if both edges have capacity left. A → C → D may be a valid path but cannot carry more flow if C → D is already full. section 1.4.2
Ford–Fulkerson repeatedly finds an augmenting path: a source-to-sink path whose edges can all carry additional flow. It adds the path’s bottleneck amount to the total, reduces the available capacity on its forward edges, and increases capacity on backward edges. Those backward edges allow later paths to redistribute flow and correct a suboptimal earlier choice. The process stops when no augmenting path remains. 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 repeated path search, bottleneck update, backward-edge adjustment, and returned flow total. section 1.4.2
The same question arises in pipelines with limited pipe capacity, data networks with limited bandwidth, and road networks with limited route capacity: how much can reach the destination through the network as a whole? section 1.4.2


