Ford Fulkerson Algorithm
Year : 1956
Family : Maximum Flow
Authors : Edsger W. Dijkstra
Time Complexity :
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem.
1 flow = 0 2 for each edge (u, v) in G: 3 flow(u, v) = 0 4 while there is a path, p, from s -> t in residual network G_f: 5 residual_capacity(p) = min(residual_capacity(u, v) : for (u, v) in p) 6 flow = flow + residual_capacity(p) 7 for each edge (u, v) in p: 8 if (u, v) is a forward edge: 9 flow(u, v) = flow(u, v) + residual_capacity(p) 10 else: 11 flow(u, v) = flow(u, v) - residual_capacity(p) 12 return flow
■ Disjoint paths and network connectivity.
■ Bipartite matchings.
■ Circulations with upper and lower bounds.
■ Census tabulation (matrix rounding).
■ Airline scheduling.
■ Image segmentation.
■ Project selection (max weight closure).
■ Baseball elimination.