given:
- a graph which represents a flow network where every edge has a capacity
- two vertices source ‘s’ and sink ‘t’ in the graph
find the maximum flow from s to t with following constraints:
- flow on an edge doesn’t exceed the given capacity of the edge
- incoming flow is equal to outgoing flow for every vertex except s and t
Algorithms That Solves The Maximum Flow Problem
|
Algorithm |
Method |
Time Complexity (Asymptotic Time) |
|---|---|---|
|
Any Linear Programming |
not practical | |
|
Augmenting Path |
O(Ef) where f is max-flow value | |
|
Shortest Path |
O(VE²) | |
|
Dinic’s Algorithm |
Improved Shortest Path |
O(V²E) |
|
Karzanov’s Algorithm |
Preflow-Push |
O(V3) |
|
Sleator-Tarjan |
Dynamic Trees |
O(EV logV) |
|
Goldbreg-Tarjan |
FIFO Preflow-Push |
O(EV log(V2/E)) |