We now present the Ford-Fulkerson algorithm and a simple explanation. To follow this tutorial, you need to understand:<\/p>\n
Take some time to review these prerequisite topics.<\/p>\n
Before we do that, recall the definition of bottleneck. A bottleneck(P, f) is defined on a path P(a simple path) on the residual graph as the minimum residual capacity on any edge of P with respect to the flow f.<\/p>\n
An s-t path in the residual graph is also known as an augmenting path<\/strong>.<\/p>\n The Ford-Fulkerson algorithm proceeds by successively augmenting each edge on the path until no path exists between s and t in the residual graph.<\/p>\n The augment procedure is given below.<\/p>\n <\/p>\n Listing 1.0: The augment procedure<\/p>\n Note that the augment procedure is performed in the residual graph to produce a flow in G. Now this augmentation procedure has to be repeated until we obtain the max-flow for G. This is a point where we can no longer find an s-t path in the residual graph.<\/p>\n The algorithm for finding the max-flow is given in Listing 1.1.<\/p>\n <\/p>\n Listing 1.1: The Max-Flow Algorithm<\/p>\n This Max-Flow algorithm is the Ford-Fulkerson algorithm.<\/p>\naugment<\/span>(f, P<\/span>)\n\tSet<\/span> b =<\/span> bottleneck(P<\/span>, f)\n\tfor each edge (u, v) \u2208 P<\/span>\n\t\tif<\/span> (u, v) is a forward edge then<\/span>\n\t\t\tincrease f(e) in<\/span> G<\/span> by b\n\t\telse<\/span> (u, v) is a backward edge\n\t\t\treduce f(e) in<\/span> G<\/span> \n\t\tEndif<\/span>\n\tEndfor<\/span>\nReturn<\/span>(f)\n<\/pre>\n<\/div>\nMax<\/span>-<\/span>Flow<\/span>\n\tInitially<\/span> set f(e) =<\/span> 0<\/span> for all e in<\/span> G<\/span>\n\twhile there is an s-<\/span>t path in<\/span> the residual graph Gf<\/span>\n\t\tLet<\/span> P<\/span> be a simple s-<\/span>t path in<\/span> Gf<\/span>\n\t\tf' =<\/span> augment(f, P<\/span>)\n\t\tUpdate<\/span> f to be f'\n\t\tUpdate<\/span> the residual graph Gf<\/span> to be Gf'<\/span>\n\tEndwhile<\/span>\n\tReturn<\/span> f\n<\/pre>\n<\/div>\n