There's sth called "redoublement". That's French. Don't be decieved. it's not that the two weeks of university lectures didn't have any effect on you. Think this through dude. :)
The teachers know the material very well, but they don't understand it, so they don't teach their students to understand it, the class just throw students in a meatgrinder that tests them on whether they "know" it.
When you go back let's say from D to A , you are just telling the node A to reduce the flow by 4 units and send it via a different network, to B in this case.
Can we go backwards just on edges that already reached full cap? I mean like 8/8 or 4/4 or 6/6 egdes? Or any edges can take us back, we just have to substract, and the number we're sending is already available on the edge: I mean for example if I have an edge which has 5/12 and I want to go backwards on this edge with 3 units. Can I do that, and I just write the new capacity of 2/12 or as long as it's not a 12/12 edge, I cannot go back? Thx in advance!!
It is important to not fall into any mental calculations (or confusion) until you are done with the complete algorithm. Yes he chose A to D thrice but if you see the final effect, A receives 10 units passes 6 to D and 4 to B. When you go back from D to A, its as if you are saying to A that you need to reduce 4 units and send them somewhere else.
i just done it! i didn´t take into account the backward edge step and i got 19 in three iterations (1: S-C-D-T= 9.....2: S,A,B,T=9+4=13.....3: S,A,D,B,T=13+6=19) is it still ok ?
I'm trying to catch up with the current semester in businessengineering and your video helped me get through ~ 50 pages of lecture in no time. Big thanks from Germany
As well as his rules about equillibrium and making sure to update the flow by the value of the bottleneck. Remember these two hard and fast rules. 1. You can only go Forward (in the correct direction of a path) if the path has FLOW TO ADD e.g 8/10 still has 2 more to add so you can use it but 4/4 is capped. 2. You can only go Backward (in the opposite direction of a path) if the path has FLOW TO GIVE e.g 6/8 has 6 to give but you can't go backwards on 0/4 because it has 0 flow to subtract.
Wow, finally someone who actually understands how to meaningfully communicate ideas to other people (what's that word called... "teaching"? But I thought that's what my university was supposed to do? hmmm........)
He have implemented the Naive Greedy Algorithm Approach (May not produce optimal or correct result) and not the Ford-Fulkerson algorithm. See the details on the link: www.geeksforgeeks.org/max-flow-problem-introduction/. The Ford-Fulkerson algorithm uses the residual graph concept, see more details on the link: www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/.
I literally watched a million lectures and spent so much time trying to understand this residual graph thing, and you just explained it in 5 minutes. Thank you, you are doing the Lord's work
I just did it using, SCDT (9) SCDBT (1) SABT (4) SADT(1) SADBT (5), with a sum of 20 which is the maximum possible. Is it wrong? Could someone please answer my question ASAP?
it is random. The only difference between going in a certain sequence rather than another sequence is it may take more iterations for some (the while loop doesn't care). But this algorithm always gets the MAX FLOW, which is what we need. The reason it never 'gets stuck' is with the use of backwards edges which allows you to essentially 'backtrack' when the edges get clogged up.
You had Ford Fulkerson for 14 weeks? We discussed this in like what... 30 minutes? + residual networks and the actual algorithm are missing here. Good video for what it's set out to do, no doubt, but 14 weeks..? lol
I can see why you could choose a path that includes D->A even though the edge actually is A->D (2:36), but my question is: Could we also use use B->C in the path? How about the edge from D to walmart? or to my house? we still can do that too, right?
I got the total capacity with 20 , with the following paths : S -> A -> D -> T = 8 S -> C -> D -> T = 2 S -> C -> D -> B -> T = 6 S -> A -> B -> T = 2 S -> C -> D -> A -> B -> T = 2 Total = 20 , with 7 saturated edges .
Thanks for the great video. I still think this thing with the backward edge push is kinda strange. So I can push 1000 if the flow against is at least 992 (because 8 capacity?)
It was my first semester in master program. The course was CS6363 Design and Analysis of Algorithms. I probably failed and wouldn’t want to check my final grade. Really bad. I def will work hard next semester.
You have implemented the Naive Greedy Algorithm Approach (May not produce optimal or correct result) and not the Ford-Fulkerson algorithm. See the details on the link: www.geeksforgeeks.org/max-flow-problem-introduction/. The Ford-Fulkerson algorithm uses the residual graph concept, see more details on the link: www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/.
If we go through path S->A->D->B->T we can include more capacity right? as we have a bottle neck of 1 at this path which is making the max capacity to 20?? Can someone clarify my query Thanks in advance
I was going to check the sources for this video to mention them in my homework, only to find out you studied at TUe as well xdxd, I dont know why but I found that extremely funny. How small the world is
The backward edge concept is hard to get. I don't understand what it is trying to do. I guess it helps even the flow in all edges. And the implementation is on another level of difficulty 😖. Then again i am a newbie.
for people looking at it and having a bipartite graph where an edge is either 0/1, you don't need to calculate bottlenecks, you just repeatedly trace a possible path.
thank you so much!!! still a little confuse about when this algorithm stops. which edges should be decided to be considered that no backward value and full of capacity?
Nice video. Thank you! Had been taught with using the residual graph and moving arrows. The idea of just using forward edges that are full or backward edges that are empty is so much easier to understand.
Your videos are really good for introducing the concepts used in algorithms! Watching this together with videos from e.g. Abdul Bari is what is getting me through this AlgDat-course.
C->A needs to be non-empty since it is a backward edge (in graph, A->C is the direction) to reach T. But it is empty. So the bottleneck being 1 (from S->C), we cannot decrease the flow in A->C from 0 to -1. That's why.
I got a small question - if one somehow chooses the smallest paths throughout the entire iterations list, could it still count as Ford-Fulkerson, or that's automatically an Edmonds-Karp implementation? I assume not, since arbitrarily should also cover the shortest paths. Thanks.
Just sitting here confused as to why you can't increase flow from (s,c) to 10/10, create a backwards edge from (c,a) and feed it 1/2, which effectively makes the output from (a,d) 7/8, outputting from (d,b) 6/6, which gives (b,t) 10/10 and a total maximum flow value of 20. Am I wrong?
this is an important algorithm where many other people explain it may go into detail and thus confused me. I looked for, like, 6~7 video explaining this algorithm, you are the best.
Thank you for these videos, I'm currently studying for algorithms & data structures exam and you are very clear in explaining how these algorithms work!
