The Essence of 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 $s$ minus the inflow into $s$).

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 $(v_2, v_1)$ were reversed, the resulting semi-path would also be a directed path.