A simple and practical max-flow algorithm.
Main Idea: Find valid flow paths until there is none left, and add them up.
Some Definitions[]
Residual Graph of a flow network is a graph which indicates additional possible flow. If there is a path from source to sink in the residual graph, then it is possible to add flow. Each edge of the residual graph has a value called Residual Capacity which is equal to the original capacity of the edge minus the current flow. Residual capacity is basically the current capacity of the edge.
Algorithm[]
Steps:
- Start with flow, f(e) = 0 for all edges, e ∈ E. Set ftotal = 0.
- Use DFS to find an s to t path P where each edge has flow, f(e) < c(e), capacity. Let f be the minimum capacity value on that path.
- Augment flow along path P:
- Add f to ftotal
- For every edge u→v on P
- Decrease c(u→v) by f
- Increase c(v→u) by f
- Repeat steps 2 and 3 until there is no path from s to t.
Analysis:
- Assumption: Capacities are integer valued.
- Finding a flow path takes O(n+m) time.
- We send at least 1 unit of flow through that path.
- If the max flow is f* then the time complexity is O((n+m)f*)
- "Bad" in that it depends on the output of the program
- Nonetheless, easy yo code and works well in practice
Edmond-Karp Implementation[]
If the residual capacity is 0, there is no edge between two vertices of residual graph. We can initialise residual graph as the initial graph as initially there is no residual flow and residual capacity is equal to original capacity. To find an augmenting path, we do a BFS of the residual graph.
Using BFS, we can find if there is a path from source to sink and also build the parent array. Using this parent array, we traverse through the found path and find possible flow through this path by finding the minimum residual capacity along the path. We later add the found path to the overall flow.
The important thing is, we need to update residual capacities in the residual graph. We subtract flow from all edges along the path and we add the path flow along the reverse edges. We need to add path flow along the reverse edges because we may later need to send flow in reverse direction.
The main idea of Edmonds-Karp is to use BFS as BFS always picks the path with minimum number of edges. So, the worst case time complexity using BFS reduces to O(VE2).