liveBook · Manning

Backward edge

As explained in The Coder Cafe

A backward edge is a residual directed edge whose capacity records flow that can be sent back to undo or redistribute previously assigned flow.

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

How The Coder Cafe covers it

How deep it goes
Works through capacity updates and an implementation loop, without presenting a formal proof.
Examples
Contrasts a 4-unit path choice with a 6-unit solution in an A-to-F network.
What it assumes
Assumes familiarity with graph paths and edge capacities while explaining backward-edge updates explicitly.
What you can do after
Build it from scratch by decreasing forward capacities and increasing backward capacities for each augmenting-path update.
How it connects
Links residual capacity, augmenting paths, depth-first search, and maximum flow.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.