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
