JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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 !
Subject Author Date
A little Doubt in Ford-Fulkerson Algorithm imrankane2005 Sep 12, 2008 at 1:46 PM EDT
Re: A little Doubt in Ford-Fulkerson Algorithm anastasov.bg Sep 12, 2008 at 3:52 PM EDT
Re: A little Doubt in Ford-Fulkerson Algorithm imrankane2005 Sep 12, 2008 at 4:04 PM EDT
Re: A little Doubt in Ford-Fulkerson Algorithm jthread Sep 12, 2008 at 5:54 PM EDT
Re: A little Doubt in Ford-Fulkerson Algorithm imrankane2005 Sep 13, 2008 at 1:26 AM EDT
RSS