JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial A little Doubt in Ford-Fulkerson Algorithm
 A little Doubt in Ford-Fulkerson Algorithm | Reply Suppose the graph is as follows -:Let it have 6 vertex {a,b,c,d,e,f} where 'a' is source and 'f' is sink.vertex 'a' is connected to vertex 'b'.vertex 'b' is connected to vertex 'd' and 'e'. vertex 'c' is connected to vertex 'd'. vertex 'd' and 'e' are connected to vertex 'f'.All edges have 1 unit capicity.Now, suppose the Augementing path finding algorithm finds the path a-b-d-f in it`s first run. Then there is no other path left in residual graph.So the Max flow in this case will be 1 but actually Max-Flow in this graph is 2 ( a-b-e-f,a-c-d-f).It seems that I am missing something here.Can any one tell me how the Ford-Fulkerson Algorithm runs in this Graph ?Thanx in Advance !
 Re: A little Doubt in Ford-Fulkerson Algorithm (response to post by imrankane2005) | Reply ```a -- b -- d -- c | | e -- f ```The following graph have a maximum flow of 1. Is this really the graph you are considering?
 Re: A little Doubt in Ford-Fulkerson Algorithm (response to post by anastasov.bg) | Reply Sorry,I forgot to mention that vertex 'a' is also connected to 'c'.``` b---d / \ / \ a / f \ / \ /  c e ```
 Re: A little Doubt in Ford-Fulkerson Algorithm (response to post by imrankane2005) | Reply In that case there is a path a - c - d - b - e - f.
 Re: A little Doubt in Ford-Fulkerson Algorithm (response to post by jthread) | Reply Thanx, I didn`t had the clearer idea of residual network.
 Forums Tutorial Discussions Maximum Flow tutorial A little Doubt in Ford-Fulkerson Algorithm Previous Thread  |  Next Thread