Take the 2-minute tour ×

i am using bfs to find augmenting path.but it is producing same path every time.but ford fulkerson algorithm requires that,we choose different path every time from source to sink,so can somebody suggest me how to modify bfs so that it produces different path every time between source and sink.graph is directed and weighted

share|improve this question
Each time use a random child. –  Ionescu Robert Jul 4 '12 at 18:12
add comment

1 Answer

up vote 2 down vote accepted

You need to make sure that the BFS ignores edges where all of the capacity has been used. Usually, the BFS is being run on the so-called residual network, in which each edge capacity tells how much capacity remains on that edge (given the flow you've sent through that edge). You can either maintain a separate residual graph, or you can have an implicit one by making the BFS look at the difference between the original capacity and the current flow for each edge (and treating an edge as absent if its capacity is zero).

share|improve this answer
but bfs chooses path based on no.vertices,i mean shortest path is based on no. of vertices from source to sink –  shalini Jul 4 '12 at 18:14
i am changing capacity but it is not helping –  shalini Jul 4 '12 at 18:17
Yes, so the first time it is run, BFS will choose the shortest path. However, after that path has been found, Ford-Fulkerson will send as much flow as possible down that path; this will use all of the capacity on at least one of the edges, thus "breaking" the path. The next BFS will necessarily find a different path because at least one of the edges on the old path is now unusable. As I said, you need to make sure that edges where all of the capacity is used will be ignored by the BFS. –  Aasmund Eldhuset Jul 4 '12 at 18:17
ok i got your point thanks :) –  shalini Jul 4 '12 at 18:22
can somebody please guide me how to use ford fulkerson algorithm for practical applications like project selection,airline scheduing –  shalini Jul 5 '12 at 16:59
add comment

Your Answer


