A backward edge is a directed edge in the residual graph that records how much previously sent flow can be sent back. It lets Ford–Fulkerson undo or redistribute flow, so an unlucky choice of augmenting path need not prevent a maximum-flow solution. section 1.4.2
Correcting a path choice
In an A-to-F network, two initially chosen paths appear to carry only 4 units in total, while a different pairing carries 6. Ford–Fulkerson does not require a smarter path-selection rule: backward edges allow later paths to revise earlier flow assignments. section 1.4.2
Whenever an augmenting path carries flow:
- Reduce each forward edge’s remaining capacity by the amount sent. section 1.4.2
- Increase the corresponding backward edge’s capacity by the same amount, creating it if needed. section 1.4.2
- Allow later augmenting paths to use backward edges to undo and redistribute earlier flow. 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 update loop pairs each forward-capacity decrease with an equal backward-capacity increase. section 1.4.2
The algorithm continues until no augmenting path remains. Backward edges are therefore part of the search for maximum flow, not a separate fix applied afterward. section 1.4.2 section 1.5
