liveBook · Manning

Edmonds-Karp algorithm

As explained in The Coder Cafe

The Edmonds-Karp algorithm is the Ford-Fulkerson method specialized to select augmenting paths with breadth-first search.

Edmonds–Karp is the Ford–Fulkerson method with breadth-first search (BFS) used to choose each augmenting path. The flow update stays the same: find a path, identify its bottleneck capacity, adjust forward and backward capacities, and add the bottleneck to the total flow. section 1.4.2

Why change the path search? The depth-first search (DFS) version has O(EU) time complexity, which is hard to predict when U is difficult to estimate. Using BFS gives O(VE²) instead, where V is the number of vertices and E is the number of edges. The bound then depends on graph structure rather than U. 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 Ford–Fulkerson loop shows what remains unchanged; Edmonds–Karp uses BFS in its augmenting-path search. section 1.4.2

How The Coder Cafe covers it

How deep it goes
Defines the BFS specialization and compares complexity bounds, but does not provide a separate Edmonds–Karp implementation.
Examples
Contrasts DFS and BFS path selection alongside a flow-update code sketch.
What it assumes
Assumes the Ford–Fulkerson augmenting-path setting while defining vertices and edges in the complexity bound.
What you can do after
Evaluate/understand when BFS path selection replaces a bound involving U with O(VE²).
How it connects
Connects Ford–Fulkerson, augmenting paths, breadth-first search, depth-first search, and graph complexity.

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.