Ford-Fulkerson Algorithm

here in front of you is a flow Network a flow network is a directed weighted graph with a source and the sink in this example I'm going to model it as a water system so you pump water through the source through the network and to the sink each one of the edges has a weight these weights tell us how much can be pumped through each pipe of your particular water system for instance we can pump 13 liters of water through this pipe five litres through this pipe 50 litres through this like 20 litres to this pack what must be conserved about flow networks is everything that comes out of the source so we pump 13 out of the source must be equal to the amount that comes in at the sink so if we pump a total of say 7 liters of water out of the source then 7 litres of water must be returned into the sink this is obviously limited by the interim weights what the max-flow problem is is what is the maximum light we can pump through this network and this is what the ford-fulkerson algorithm solves so we're going to go through a worked example of the Ford Focus in other word as you can see from the algorithm in front what the ford-fulkerson algorithm does is while a path exists from the source to the sink say we go from the source to V 1 V 1 to V 2 V 2 to V 3 and V 3 to V 4 and V 4 to the sink while such a path exists the port focusin algorithm says calculate the residual network of that path and then repeat you may be wondering what some residual Network well I'll show you in this example so first of all we find a path from the source to the sink so we go from the source to V 1 to V 2 to the sink we can clearly see there's a path in order to pump water along this path we have to choose the smallest value which in this case is 3 so we pump 3 liters of water from the source to V 1 V 1 to V 2 and V 2 to V 3 as we have pumped three litres of water along this path that means 3 litres of water has been pumped on here so we will ten of 13 to your 5 and 0 of 3 is that is the residual amount we have left we then drop backwards labeled Arab stating how much we have pumped 3 that already 3 pump three a pump 3 and we pump 3 here is therefore what the residual network looks like next as ford-fulkerson States we want to continue this until no such path exists from the source to the sink so we'll pick another path for instance source 2 V 3 V 3 2 V 4 and V 4 to the sink we were able to pump 10 liters of water along this as 10 is less than 35 unless than 20 so we pump 10 liters across here giving us with none left and a backwards arrow of 10 we pump 10 liters leaving us with 25 or 35 and a backwards arrow of 10 and from the sink to V 4 where the backwards out of 10 so so far we have pumped 3 and 10 liters of water again as for foot person States we try and find another path and there is one available if we go from the source to V 1 V 1 V 2 V 2 V 3 V 3 2 V 4 and V 4 to the sink that will do that still have a remaining 10 we were able to pump here two-wheeled pump here 50 25 and 20 obviously 2 is the least of it so we pump - this will therefore become 8 this will become 5 as we are pumping 2 extra backwards this will become 0 again 5 this year will become 48 of 50 with a big backwards arrow 2 this will become 23 this will become 12 this will become again because we're pumping 2 litres of water around our system and this as well 12 we've pumped another two liters of water around our system if we go back to the algorithm it says well no such path exists so we look at our graph again we can tell that there are no paths exist as if we go from the source you cannot go this way as there is ZERO black room left on water we go this way we're able to pump eight but unfortunately here from v1 to v2 again there is zero so there is no path left from the source to the sink therefore the maximum flow of our network is 50 and this satisfies our condition at the very start that whatever leaves the source must enter in at the sink if you're wondering what the increased max flow counter of the algorithm does this is simply a variable that holds the total sum of all the max flows of all the paths throughout the whole graph ie this part of the worked example I've included this section in the video as I simplified the working example to make it easier to understand but you'll hear a lot of these terms thrown around online for instance augmenting paths what is an inventing path on the menteng path is simply the path we take from the source to the sink as seen here in the work example the residual capacity the residual capacity is the capacity of an Augmented path so in other words it is the total flow pushed along that path and lastly residual Network I briefly mentioned earlier what this was but just to recap here it is again it is really the resulting network after the Augmented path has been applied the time come back to this algorithm is e times the maximum F where E is the total number of edges and Max F is the maximum flow that we would calculate using this algorithm okay so I'm going to quickly draw a graph with a source to the sink at the end these with we it's 500 500 500 501 and what let's switch to the red pen as Ford Fulkerson algorithm states we need to find paths to augment a best-case scenario would be if the algorithm chose s to V 1 V 1 to T or equivalently s to V 3 and V 3 to t but worst case our algorithm chooses s to V 1 V 1 V 2 V 2 to V 3 V 3 to T in that scenario the minimum capacity of the invented path the algorithm chose is 1 therefore 3 this 0.499 backward 0 of 1 2 here this will come 0 I will pump 1 back this will become 0 will push 1 back listener also become 499 i'm fish 1 back next the algorithm may choose SD V 3 V 3 2 v 2 e 2 2 V Rho 1 and T this will become 4 9 9 in case I didn't make clear earlier you may traverse the backwards arrow you've created in your residual networks so this will return back to one while this becomes 0 this will return back to 1 as this becomes 0 this will come 499 again the backwards arrow of 1 you may see a pattern that has developed we may not keep continuing this pattern of going from s to V 1 V 1 to V 2 V 2 V 2 to V 3 and V 3 to T and then do s to V 3 to be 2 to be 1 to T the maximum capacity of the entire flow of the network will increase by 1 on every iteration and this will keep happening until all 1000 has become out of the source I'm received at the same level equal 1000 this means on a worst case scenario we will have to find a path through your graph 1,000 times to remind ourselves of the complexity the reason it is easy of an event is because it can take up to any number of times to find a path throughout the network for example if the network was this source to v1 to v2 to the sync every time you want to define a path throughout the network it would be equal to the same number of edges that exist within your network tarika the reason it is e of M of F is because it may take any times to find the path and you may have to find it maximum flow number of times lastly there are some things to note when using the ford-fulkerson algorithm on a flow Network personally euro me light one source so as you can see from the example below we have two sources there's an easy way to fix that and that is to simply create a new source s0 with arbitrary large value weighted values coming out of it so an example per thousand the same with the sink you're only allowed one sick so we'll call that T zero as well lastly when starting your algorithm there should be new parallel edges so we include this in the graph this here as a set of Humpty parallel edges this is very simply solved all we do is add a new vertice unlink from V 1 to V 3 V 3 to V 2 and V 2 to V 1 thank you I hope that improves your understanding for the ford-fulkerson algorithm for calculating the max flow of flow Network

Channel: James Burnside

Views: 69,307

Keywords: Ford Fulkerson

Id: v1VgJmkEJW0

Length: 9min 59sec (599 seconds)

Published: Sat Jan 11 2014