liveBook · Manning

Augmenting path

As explained in The Coder Cafe

An augmenting path is a source-to-sink path in a residual flow network along which additional flow can be sent.

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

How The Coder Cafe covers it

How deep it goes
Defines the path condition and works through bottlenecks, capacity updates, and repetition without requiring a specific path-finding method.
Examples
Contrasts two short paths by remaining capacity and uses flow-network scenarios involving pipes, data links, and roads.
What it assumes
Assumes familiarity with graph vertices and edges while defining source, sink, and augmenting path before using depth-first search.
What you can do after
Build it from scratch by finding augmenting paths, updating forward and backward capacities, and stopping when no path remains.
How it connects
Connects maximum flow and Ford-Fulkerson to bottleneck capacity, depth-first search, and backward edges.

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.