liveBook · Manning

Ford-Fulkerson algorithm

As explained in The Coder Cafe

The Ford-Fulkerson algorithm computes a maximum flow in a capacitated flow network by repeatedly augmenting flow along available paths.

The Ford-Fulkerson algorithm finds the maximum flow that can travel through a network from a source to a sink without exceeding any connection’s capacity. Think of water moving through pipes, packets through network links, or cars along roads: the question is how much can reach the destination at once. section 1.4.2

A flow network has vertices connected by directed edges. Each edge has a capacity—the most it can carry—and a flow—the amount currently passing through it. The source is where flow starts; the sink is where it ends. section 1.4.2

Ford-Fulkerson increases the flow one augmenting path at a time:

  • Find a path from source to sink whose edges all have room for more flow. If none exists, return the accumulated flow. section 1.4.2
  • Find the path’s bottleneck, then reduce the available capacity of each edge on the path by that amount. section 1.4.2
  • Increase the corresponding backward-edge capacities. These allow later paths to redistribute flow if an earlier path choice was suboptimal. section 1.4.2 section 1.5

A path is not necessarily usable

A → B → D is an augmenting path when both edges have remaining capacity. A → C → D may still connect the source to the sink, but it cannot carry additional flow if C → D has no capacity left. 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 Python sketch shows the repeat-and-update loop. It leaves path finding, bottleneck calculation, and backward-edge lookup to helper functions. section 1.4.2

How The Coder Cafe covers it

How deep it goes
Explains terminology and the update loop, but leaves augmenting-path search and bottleneck calculation to unspecified helpers.
Examples
Contrasts usable and blocked paths and motivates maximum flow with water pipelines, data networks, and traffic routes.
What it assumes
Defines flow-network terms and augmenting paths before applying the algorithm.
What you can do after
Evaluate/understand how repeated path augmentation increases flow and how backward edges correct suboptimal path choices.
How it connects
Connects flow networks, augmenting paths, edge capacities, bottlenecks, 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.