Ford-Fulkerson Algorithm

This is the naïve solution to the Max flow problem. It runs in pseudo-polynomial time depending on the size of the solution. A more developed algorithm that uses the same design is the Edmonds-Karp algorithm.

Their main difference is that Edmonds-Karp algorithm must use BFS whereas Ford-Fulkerson Algorithm can use DFS also. For a runtime bound we require Ford-Fulkerson Algorithm to use integer capacities.

Algorithm

ford_fulkerson(G, c, s, t)
	Input: A flow network with integer capacities.
	Output: A max flow on the network.
1. Set f(e) = 0 for all e in E.
2. Build the residual network G^f for the current flow f.
3. Check for any s-t paths p in G^f using BFS (or DFS).
	1. If no such path then output f.
4. Given p let c(p) = min_{e in p} c^f(e).
5. Augment f by c(p) units along p.
	1. f(e) = f(e) + c(p) for forward edges.
	2. f(e) = f(e) - c(p) for backward edges.
6. Repeat from step 2.

Correctness

This is proven as flows are maximal if there is no augmenting path in the residual graph. The proof of this follows from the Max-flow min-cut Theorem.

Run time

If we assume are integers, then each iteration we will increase the flow by 1. Therefore we can have at most the max flow iterations .

To run each iteration we need need to update the path length number of edges in the graph which takes time. We need to run BFS which takes if we assume is connected. Then calculating and updating the weights also takes time. So all together a single iteration takes time.

Therefore altogether the runtime is .