Ford–Fulkerson algorithm

Lore & Background

The algorithm works by repeatedly finding a path from the source to the sink with available capacity on all edges—called an augmenting path—and sending flow along it. This process continues until no more augmenting paths can be found in the residual network, at which point the flow is maximal. The residual network is defined with capacities equal to the original capacity minus the current flow, and it may allow flow in directions not originally present.

Reader's Guide

The Ford–Fulkerson algorithm is foundational in network flow theory, underpinning many practical applications such as transportation, telecommunications, and bipartite matching. Its significance lies in its simplicity and the proof of optimality via the max-flow min-cut theorem. However, the algorithm's runtime is not guaranteed to terminate with irrational flow values; with integer capacities, the runtime is bounded by O(Ef), where E is the number of edges and f is the maximum flow. The Edmonds–Karp algorithm, a specific implementation using breadth-first search, is often also called Ford–Fulkerson. The method can be extended to handle multiple sources and sinks by adding a super-source and super-sink, and node capacity constraints by splitting nodes.

Did You Know?

• The Ford–Fulkerson method is sometimes called a 'method' rather than an 'algorithm' because the way to find augmenting paths is not fully specified.
• The name 'Ford–Fulkerson' is often also used for the Edmonds–Karp algorithm, which uses breadth-first search.
• When capacities are integers, the runtime of Ford–Fulkerson is bounded by O(Ef), where E is the number of edges and f is the maximum flow.
• The algorithm may not terminate if flow values are irrational.