Sharkey: Applying the Augmenting Path Algorithm to Solve a Maximum Flow Problem

all right well hello welcome to this video what we're going to do is we're going to figure out the maximum flow that can go from node 1 to node 6 in this network by applying the augmenting path algorithm to find the max flow what we'll do towards the end is we'll talk about how we can use the final residual network in augmenting path algorithm to figure out what the min cut in this network is as well what we're looking at right now is a network with the arcs each arc in the network is labeled with its capacity so the first step in applying the augmenting path algorithm is we need to create the residual Network associated with the current flow currently we haven't put any flow on any of the arcs it so current flow on all these arcs are zero so right now we have that X IJ is equal to 0 for all arcs IJ now if you remember what a residual capacity of an arc is its if it's a original arc in the network so for example r12 is an original arc in the network it's the unused capacity of that ox so since x12 is currently 0 the capacity of arc 1 2 is 3 we have a certain ridge of the pasty of 3 now there's also kind of residual capacities of the backwards arcs for the arcs in the network so we have the concept of route zero capacity of arc 2 1 that is the amount of flow that's equal to the amount of flow currently on arc x12 on art 1 2 and that residual capacity represents how much we can decrease the flow on arc 1 2 by in walking backwards along the arc 2 1 so that's the definition of the residual capacities for both the 4 and backwards arcs what is nice is based on those definitions the residual capacities of the network when all the flows are 0 are simply the capacities of the arcs in the network and all the residual capacities of the backwards are set equal to 0 so what we can essentially do is we can start working with this network and instead of having UI J we really have our IJ already given to us so we're going to just kind of move on to the next picture and all that change from that previous picture to this previous picture is we have the R IJ designated up top now we're interested in maximizing the flow from node 1 to node 6 so the way the augmenting path algorithm works is that first step is we're going to determine if we can find a path from node 1 to node 6 in the residual Network any path will do there is kind of a an advantage of taking paths that contain a small number of Arc's so that's kind of be our initial goal so if I look I can start at node 1 I can take arc 1 2 I can then take arc 2 4 and then I can take arc 4 6 so the red arcs are a path from 1 to 6 in the residual network composed of arts with positive residual capacity so our path P is composed of arcs 1 to R 2 4 and then arc 4 6 and what we're going to do along this path is we are going to use it for all it is worth so we're going to try and put as much flow on this path as possible equivalently the amount of flow we're going to augment along this path is equal to the minimum of the residual capacities of the arcs on the path so we're looking at min R 1 to R 2 4 and R 4 6 and currently turns out that all of these arcs have residual capacities of 3 so I know what I'm going to do is I'm going to push 3 units of flow along this path by doing so I'm going to have to change the residual capacities of both the forward arcs and the backwards arcs along this path for forward arcs so R 1 2 we are going to decrease its residual capacity by the amount by this delta amount by the amount we're pushing along the path so rizzuto passive arc 1/2 is going to decrease from 3 to 0 because we're pushing 3 units of flow along it so arc 1 2 is going to disappear from our residual Network because once you have a reserve capacity 0 you're no use to us anymore in the residual residual Network now for the backwards r21 we just put 3 units of flow on arc 1 2 so that means potentially we can decrease the flow on arc 1 2 in later stages so that means will increase the residual capacity of arc 2 1 by the amount Delta that we're pushing along so what we're going to do is we're going to go to kind of the bare-bones next network what we will do is we'll just simply copy over the residual capacity of the arcs that are unaffected by that path we just did so presume to pass C of 1 3 remains for reserve capacity of 3 5 remains 2 residual capacity of 3 4 remains 1 residual capacity of 2 5 remains 1 and the residual capacity of 5 6 remains 5 and now we're going to replace and how to update the residual capacities of the arcs along the path so like I said before we're going to push 3 units of flow along arc 1 2 which means its original path is going to decrease to 0 it's not lonely no longer to appear in the network but the backwards arc from 2 to 1 will appear with the residual capacity of 3 arc 2 4head / zu capacity 3 before we push 3 units of flow on it so it's rigid opacity drops to 0 but we are going to push we are going to have our 4 to appear in the network the reserve capacity of 3 same story for 4 6 its regional capacity started 3 push 3 units of flow along the path it drops down to 0 so arc 4 6 disappears from the residual capacity residual Network and then our for 6 appears with the residual capacity of 3 so what we've basically done here is we have successfully implemented one step or one iteration of the augmenting path algorithm and we repeat we basically now look at this network and try and find a path from node 1 to node 6 so in this case again we're going to go with kind of shorter paths will move from 1 2 3 move from 3 to 5 and then we can move from 5 to 6 and reach node 6 so our path P contains arcs 1 3 3 5 and then 5 6 and then we're going to look at calculating our Delta so how much flow we're pushing along this path by looking at the minimum of the residual capacities video dark so min are 1 3 are 3 5 and are 5 6 which is equal to the minimum of 4 2 & 5 so our residual capacity or the Delta how much flow pushing along this path is set equal to 2 and we're to do similar updates to what we just did in the previous step we're now need to update the residual capacities of all the arcs along this path so first thing I'm going to do is I'm going to draw in the arc set in the network that were not included in this path so the residual capacity there those arcs and they're backwards arcs will not change so I'm doing all the arcs didn't appear nothing changes about them or they're backwards arcs and now for each of these red arcs I need to update the residual capacities I'm going to decrease the amount of pushing along this path is 2 I'm going to decrease their residual passage by 2 and increase the rizzuto pass through their backwards arcs by 2 so we still have arc 1 3 it had original path C 4 we're going to decrease it by 2 so it ends up with reserve capacity to r3 1 how to reserve capacity 0 since it's the backwards arc we're going to increase the residual capacity by the Delta Oracle limit - so arc 31 now has a back Pasi of three arp three five had a residual capacity of two we decrease by two it ends up having reserve capacity zero so it leaves the network but we add an arc five three with the residual capacity of 2 and then five six how to reserve capacity five it decreases to having a residual capacity of three and then in the back words are six five ends up with the residual capacity of two and we repeat we have another residual network we try and find a way to go from one to six so looking at this network I can leave node one I can go from node 1 I can go to then node three from node 3 the only way out and node 3 is to go from 3 to 4 only way to get out a note 4 in the residual network is to go to node 2 only way to leave node 2 is to head towards node 5 and the only way to get out of note 5 is to head towards node 6 which is good because we just found another path from 1 to 6 so I'm happy we can push flow along this path so our path P is composed of arcs 1 3 3 4 4 2 2 5 and then 5 6 and again our Delta is equal to the min of the min across all arcs in path P so any arc in path P of our I J and so we're taking the minimum of 2 1 3 1 & 3 so this Delta is going to be equal to 1 we're both arcs 3 4 and 2/5 had their residual capacities equal to 1 so this is a little bit more of a complicated problem to kind of are this more not complicate problem complicated residual Network to update because so many of the residual arcs will have their flows changed so again we'll just start by drawing the flows on the arcs where the that are not impacted by this change in the residual capacity or change in this the path not impacted by the path we just selected so now we're going to push one unit of flow along the red path so we need to decrease the residual passage of the forward arcs in that path by one and increase there's no capacities of backwards arcs by one so our 1 3 will still be in the residual Network now it just has a residual capacity of instead having two we decrease it by one has a drug capacity of 1 and then our 31 had a residual capacity to it updates to having residual capacity of 3 arc 3 for header 0 capacity 1 in search of the past decreases to 0 but we increase the reserve capacity backwards our from 4 to 3 to 1 now if we look at arc 2 4 or sorry not arc 2 4 4 2 s Rideau capacity was 3 we're going to decrease that by 1 to 2 and then now we reintroduce our to 4 into the network it had a residual capacity 0 but we're increasing it to 1 because we walked along it's backwards equivalent so we walked along the forward arc for to so it's backwards equivalent is 14 are 2 5 hydrogen has 1 extra capacity drops to 0 so now I have a backwards arc from 5 to 2 with the residual capacity one and then arc 5 600 passed III it's rigid Pasi drops to 2 and then we increase through the capacity the backwards arc by 1/3 and now what we can doom in this network is see if we have a path from 1 to 6 so if I start at node 1 only way out of note one is to go towards node 1 to node 3 once I get to know 3 I can't leave no.3 there's no way out unless I go back to 1 it doesn't really help me get towards node 6 so we can stop there is no path from 1 to 6 so that means we're done with our augmenting path algorithm we found the max flow in order to get the flow levels of the arcs what we can look at is we can look at the residual capacities of their backwards arcs so what we know currently is that I have a resume opacity of 2 1 which implies that I have 3 units of flow on arc 1 2 so X 1 2 is equal to 3 X 1 3 is equal to 3 and then looking at X 2 4 it's backwards arc for 2 a 0 to the past 2 so X - 4 is 2 and X let's look at X 3 5 it hazards if I see of 2x - 5 has your joke that's it none X - 5 has a flow of one because the backwards arc 5/2 is Rizzuto capacity of 1 and then what a arcs are we missing here X 3 4 has a flow of one because arc 4 3 has residual capacity of 1 and I forgot to write down there is a passive 4 6 6 4 so X 4 6 hazard flow 3 because X 6 4 hydrogen capacity arc 6 4 hundreds of capacity of 3 and then we also last one when it put in is X 5 6 has a flow of 3 on it because arc 65 had a residual capacity of three and we're good we found the flow we found the max flow now one thing I wanted to kind of indicate is that let's look at how we can possibly get the min cut currently right now in my final network I can only move from one to three the only node I can reach from node 1 is node 3 so let's look back at our network here and actually I mean if you do the math on the flow balance will work out and this ends up with a total flow equal to 6 which is the total amount of the deltas over all iterations of the augmenting path ok so now we can look at is I can move from 1 and this is the original network with the residual with the original capacities 1 & 3 are the only nodes that have a path from 1 to 3 in the final residual network and what I want to do is look at the cut that separates 1 & 3 from the rest of the network if I look at that cut the cut capacity is u1 2 Plus u 3 4 plus u3 5 which is equal to 3 plus 1 plus 2 which is 6 so if we want to find the min cut in the network as well when we're done with plying the augmenting path algorithm figure out all nodes that can be reached from our source node in this case node 1 all nodes that have a path in the residual Network they're going to form one side of when if you look at the arcs in the mid cut those nodes that can be reached from the source node will form one side of be cut and the reason why one we using we know that this is the min cut is because the cup capacity of this cut is equal to a feasible flow level that we identified with the in with the augmenting path algorithm so we know that the max flow in the network is 6 and the min in the network is six so that concludes this video um and I will see you around

Channel: ORMethodsTutorials

Views: 45,987

Keywords:

Id: 6jq52v6Gkts

Length: 17min 46sec (1066 seconds)

Published: Thu Sep 25 2014