What is a Ford-Fulkerson algorithm?
Ford-Fulkerson algorithm finds the maximum flow through a network or graph through a greedy approach.
Flow graph
We find the maximum flow using a flow graph. A flow graph has edges that have a maximum capacity that cannot be exceeded. Edges also have a flow value, which is the number of flow units that can pass through an edge. There are two particular types of nodes in a flow graph:
The source node is the one that sends a value. It is usually denoted by s.
The sink node is the one that receives a value. It is usually denoted by t.
This is an example of a flow graph:
The fraction adjacent to each edge specifies a flow and the capacity value. The flow is the amount of data passing through an edge, and capacity is the maximum amount of data that can be passed through an edge. In the example above, we have a capacity of 10 for the edge while the capacity of edge is 25. Initially, the flow through each edge is zero, and the capacity is a non-negative value.
The fraction adjacent to each edge specifies a flow and capacity value. The flow is the amount of data passing through an edge, and capacity is the maximum amount of data that can be passed through an edge. In the example above, we can have a capacity of 10 for the edge while the capacity of edge is 25. Initially, the flow through each edge is zero, and the capacity is a non-negative value.
Residual graph and augmenting path
A residual graph is a graph that has additional possible flow. For example, if a flow of 10 bits is passed through an edge with a capacity of 25 bits, we have an additional space of 15 bits to pass through that edge. So, that graph will then become the residual graph.
An augmenting path is a path of edges in the residual graph with an unused capacity greater than zero from the source s to the sink t.
Maximum flow
Maximum flow is the amount of data we can push through a network from the source node to the sink node without exceeding the capacity of any edge. In other words, the maximum flow is a bottleneck value for the traffic your network can handle from source to sink under all constraints.
The algorithm proposes that we achieve maximum flow when no more augmented paths are left to be found. To find the maximum flow, the Ford-Fulkerson algorithm repeatedly finds the augmenting paths through the residual graph and augments the flow until no more augmenting paths can be found.
Note: Remember that the key point about an augmenting path is that it can only flow through edges that have extra capacity and are not saturated yet.
Residual capacity
Every augmented path has a bottleneck value: the smallest edge on the path. We can find the bottleneck value by taking the difference between the capacity and the current flow of an edge, known as the residual capacity. We can use this bottleneck value to augment the flow along the path.
Augmenting the path
Augmenting the path means updating the flow values of the edges along the augmenting path. For forward edges, this means increasing the flow by the bottleneck value.
Example 1
We chose two different paths in this example. There wasn't any path left without a saturated edge, so the maximum flow was 20 without reverse paths. Now we will see an example with reverse paths.
Example 2
While augmenting the path, we don't only need to increase the flow but also decrease it along each residual edge by the bottleneck value when there is a reverse-path included. Let's look at the example below:
In this example there is a reverse path from . So we got the maximum flow of 6 by using a reverse path. As there are no more augmented paths left.
The maximum flow is used in many situations where edges and nodes can represent any number of things. For instance, the edges can be water pipes, wires with electric current, and so on. Each of them has a certain capacity value. The maximum flow represents the volume of the water that could flow through the pipe or the net electric current that the system can sustain.
The Ford-Fulkerson method's time complexity depends on the algorithm used to find the augmenting paths.
Free Resources