...

/

The Essence of the Ford-Fulkerson Algorithm

The Essence of the Ford-Fulkerson Algorithm

Understand the essential idea behind the Ford-Fulkerson algorithm.

The Ford-Fulkerson algorithm is used for finding maximum flow in a flow network. It can also be used for the dual problem of finding a minimum cut. We defer discussion over minimum cuts to the next lesson.

Recall: A maximum flow is a flow with maximum value (where the value of a flow is the outflow from the source ss minus the inflow into ss).

The core idea

The Ford-Fulkerson algorithm employs the idea of increasing the flow in each round along some semi-path. By a semi-path, we mean a directed subgraph whose edge orientations if removed constitute a simple undirected path between source and sink.

For example, the following is a semi-path but not a directed path. If the orientation of (v2,v1)(v_2, v_1) were reversed, the resulting semi-path would also be a directed path.

Press + to interact
An s to t semi-path with labeled edge capacities
An s to t semi-path with labeled edge capacities

For a semi-path starting at the source vertex, we classify its edges in one of the following ways.

  1. Edges like (s,v1)(s, v_1)
...