Understanding the Ford-Fulkerson method
The Ford-Fulkerson method uses the max-flow min-cut theorem to solve the maximum flow problem for flow networks. It is called a method because some parts of its protocol do not specify implementation. A method is a more general algorithm where individual steps can be implemented differently. For the Ford-Fulkerson method to work, a graph should have at least one source and sink node, where the maximum flow must be calculated from the source to the sink. Consider the flow network below, where values in edges denote their maximum capacity.
A flow network with source and sink where edge weight denotes the capacity of an edge.
Algorithm
The Ford-Fulkerson method starts by initialising a variable maxFlow to 0 and repeatedly tries to find an augmenting path in the residual graph. If an augmenting path is found, it gets the minimum capacity of the edges in the augmenting path in a variable pathFlow and adds it to maxFlow. It then simulates the flow (pathFlow) through the augmenting path in the residual graph to generate a new residual graph for the next iteration. This process is repeated until an augmenting path can no longer be found, at which point the value in maxFlow denotes the maximum possible flow in the graph.
To better understand the algorithm, let's examine the first two iterations in the method using the following graph.
A flow network with source and sink where edge weight denotes the capacity of an edge.
We start the method by initializing a variable maxFlow which keeps track of the maximum flow in the graph. Then, we initialize the first residual graph residualGraph and set the capacity of all edges equal to the capacity of the edges in the input graph.
The residual graph at the start of the Ford-Fulkerson method.
Liking the course? Check our discounted plans to continue learning.