Week 7 - Ford-Fulkerson Algorithm

This lecture will focus on the Max flow problem. To define this we need some other definitions.

Flow network

Flow network

A flow network contains the following data:

• A directed graph ,
• An edge weighting called the capacity,
• A source , and
• A sink . This can be summarised as .

Link to original

Flow

Flow

Given a flow network a flow is an allocation such that the following holds:

• capacity constraint: for all , and
• conservation of flow: for all .

The size of this flow is .

Link to original

Statement

Max-flow problem

Given a flow network what is the max value a flow on this network can have?

Link to original

Assume we have no parallel edges

If we are in the case where there are parallel edges, we can split one edge into two by putting a vertex in the middle of it.

We will assume from now on we have no parallel edges.

Algorithm idea

We want to build a flow by finding paths from to in a flow network. However, if we greedily pick paths we do not get an optimal solution.

We may have to backtrack on previous chosen paths if it means we can increase the net flow. So lets define the residual network for a flow .

Residual Network (flow)

Residual Network

Let be a flow network and be a flow. Further assume has no dual edges. Define the where and capacity The let the residual flow network be .

Link to original

This allows us to define the idea for the algorithm.

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.

Link to original

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 .

Link to original