Ford-Fulkerson Algorithm

The Ford-Fulkerson Algorithm is a greedy algorithm for calculating maximum flow in a flow network.

Note

The central idea behind the algorithm is as follows: As long as any path exists from the source node to the sink node that has residual capacity, we send flow along one of the paths.

If more than one path is needed, these are known as augmenting paths.

---

Complexity

The complexity values for the Ford-Fulkerson Algorithm are:

Aspect	Complexity
Time	$O(\Vert V\Vert E^2)$
Space	$O(V)$

---

Example

What is the maximum possible flow through this graph from $s$ to $t$.

The maximum flow going out of the source node, $s$ is $10+5=15$.

Hence, we are free to send the full $10$ into $u$ and the full $5$ into $v$.

However, $u$ can only output $5$ into the sink node, hence we must send $5$ down to $v$ before outputting $10$ from $v$ and $5$ from $u$ into the sink node.

Link to original