Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)
ฝัง
- เผยแพร่เมื่อ 26 ต.ค. 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Flow Networks: en.wikipedia.org/wiki/Flow_ne...
Ford-Fulkerson Algorithm: en.wikipedia.org/wiki/Ford%E2...
Max-Flow Min-Cut Theorem: en.wikipedia.org/wiki/Max-flo...
Proofs: Reference "Algorithm Design" by Jon Kleinberg and Éva Tardos Chapters 7.1, 7.2 for excellent proofs on all of this.
Things I'd Improve On This Explanation (w/ More Time):
1.) I should have done a walk-through showing how the residual graph dictates how the original graph's edge flows (f(e)) are updated each iteration. (That would've made it more clear how the residual graph in the Ford-Fulkerson algorithm tells us how to update the flow on each edge (f(e)) in the original graph along the s-t path P, THEN we update the residual graph (also along P) to prepare for the next iteration.)
2.) Go into the actual augmentation once we find an s-t path P in the residual graph. We can only modulate the flow f(e) for each edge in the original graph on path P ± the smallest value residual graph edge on path P. The smallest forward edge on path P in the residual graph is the "bottleneck" to how much we can increase flow along the path P in the original graph. (hard to visualize...the textbook may have to take it away with this one, but when you understand this you'll really get it after watching this video)
I also didn't talk about time complexity, but the amount of while loop iterations is bounded to the capacity coming out of start node 's'. We can't ever push more flow from 's' than the sum of capacities of those exiting edges. If each interaction increases the value of the flow v(f) by 1 (and v(f) starts at 0 in the beginning since no "water" is going through the "pipes"), we can do at most C augmentations of the flow network where C = sum(edge capacities leaving 's').
In each while loop:
- O(|V| + |E|) to find the augmenting path
- O(|E|) to update the flows in the original graph
- O(|E|) to update the residual graph
So total runtime can be bounded to O(C * (|V| + |E|)).
#backtobackswe #benyamephrem - วิทยาศาสตร์และเทคโนโลยี
![หมานแต่ผัวเขา - แสตมป์ โตเกียวมิวสิค [ OFFICIAL MUSIC VIDEO ]](http://i.ytimg.com/vi/m0g1TSBJPgo/mqdefault.jpg)
Ben your stuff is also helpful for senior devs(like myself). I’ve just landed a job at Amazon SA CPT. Thank you young man. Continue doing what you do.
Congrats, happy for you
> Textbooks could do 10 times of a better job than I could ever do.
Textbooks could stretch out what you described in this video to be 300 pages. This is beautiful and is more than I learned from a week of Algorithms. Thank you!
You already have achieved the minumum cut..Cause you(source) are clearly trying to maximize the amount of flow of knowledge that can reach us(sink)..
Well done bro..
well put
This was really helpful! I'm studying to be a data engineering and we talk a lot about graphs so your videos really help. You are very clear and explain things in a very visual way which helps a lot. Thank you so much!
First year Computational Science student here. Thanks a lot for your videos, man. They're really helping me for my Data Structures & Algorithms class
This 20 min video was more clear than a whole chapter of a book or any other lecture! Thanks for this beautiful explanation :D
Happy Holidays 🎉 Thank you for this beautiful comment, tvishathakur! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
There aren't enough good words in the world to describe my gratitude towards you and the videos you make!
May the internet grow big and strong
This is literally the best video I've seen for explaining the min-cut problem.
Check out the free DSA Mini-Course 👉backtobackswe.com/five-day
Table of Contents:
Defining The Flow Network 0:00 - 3:35
Greedily Pushing Flow 3:35 - 5:16
Recovering From The Greedy Choice 5:16 - 8:01
The Residual Graph 8:01 - 15:36
Ford-Fulkerson Algorithm (Overview) 15:36 - 17:42
Max-Flow Min-Cut 17:42 - 21:55
Thanks so much for this channel dude. Your videos on backtracking and sorting were absolutely key to my technical interviews at Amazon this past week. Ended up getting an offer, cheers mate.
Nice!
@@BackToBackSWE So as far as i understand the min cut (S,T) is an indication/bottleneck for the maximum flow we can push if all outgoing edges of the S part become saturated,right?
@@BackToBackSWE What purpose does a cut serve ?
This is so helpful! I memorized Ford-Fulkerson algorithm but never got an intuitive understanding until I saw this video. Thanks!
nice
Dude, best explanation ever. I tried looking at 4 different videos, yours is the best.
DUDE. I am still really early on in your videos but just wanted to come to your latest video and say.Your videos are incredible they are such an enormous help. The amount of research and thought you put into each video Is very clear in how well you explain all of the concepts you cover. Thank you very much for all your hard work. I appreciate it and godspeed brother wishing you all the best in your career and studies.
thanks
This is amazing, thank you so much for explaining what the residual graph actually means. I've studied the proof but never understood it fully until now.
Watched like several videos on this topic, and this video by far the most clear and concise.
nice
Please continue to do this series of lectures!!! You are way better than my teacher in college.
Thank you for explaining why we can traverse backwards edges when finding an augmented path. Most other resources seem to gloss over this when it's the trickiest part of the algo!
yeah
THANKS a ton! You're explanation of max-flow min cut was so valuable, better than my course lectures.
perfect. thanks so much.. spent hours watching lectures and this one vid helped me more than all of them combined!!!!
Great Tutorial man. It saved me the pain of reading a whole paper. Thanks. This is a really good explanation. One can go back and code without much of a problem.
ye
This is actually the best source out there which simplifies and explains properly!
i agree :)
Great. It really helps seeing a fellow human being gesticulating and talking and drawing. I never thought about it, but it really helps binding my attention. Thanks, my dude.
Your ability to transmit information in a clear and complete way is golden.
Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
Thank you for your help, I'm currently studying in year 12 in Australia and this is really helpful, Thank You!!!
5 mins in and I’m subbed. These videos are true gems. Thank you very much
ur a gem
The choice of example was perfect. Simple but complex enough to illustrate the need for backflow. Great video for the intuition.
ye
Big Thanks from a novice com-sci student here! I couldn't follow this in class but you explained everything clearly!
Happy to help!
God, thank you so much for this video. I was pulling my hair out reviewing some modules before my upcoming final. This clarified things so much!!
Mathematical engineering student here! Thanks man, this is helping me with my OR exam!
nice
This video was fantastic, I needed a visualization badly. Thank you so much
Excellent teaching skills! I finally understood the concept now! Thanks a lot :)
Really well explained the intuition. Exactly what I was looking for!
great.
best lecture i ve found so far, thanks!
Thank you so much for this video, I've been struggling to understand this for awhile.. Buh now I get it..
So glad I found your channel!! Your explanations are so clear :)
Welcome to the channel.
Thank you for making this great video! :) It's helping me with my graph algorithms course.
Well done! Thank you very much for your work putting together this helpful video
I'd like to thank you cause I didn't understand anything my professor told us in class, and his slide were also a mistery until I saw your video.
nice
Are you also in Asif Salekin's class?
@@orderkare7907 ?
literally one of the best explainations
Many thanks from graduate students at the Faculty of Electrical Engineering and Computing, Zagreb, Croatia!
Amazing video!
Thank you!! You make it so simple. Keep on, it's great!!
So clear! Thank you! I find the textbook stuff is so bogged down with notation that I have a hard time seeing the intuitions. You made it crystal clear!
Glad it was helpful!
Amazing Explanation! You have some great communication skills for a topic that is definitely not the easiest
thanks
Best video on this subject! Thank you!
Thank you a lot for this!
This has helped me a lot with my presentation
Thank you so much, you made this so much more understandable than my instructor
Thanks 🙏🏻
Your way of explaining is perfect
Really love the word "undo". It help me understand what the hell there's an reverse arrows in this algo
Found your video literally a day before my exams. Thanks heaps
yo
Glad I couldn’t find any German videos on this topic, this is great!
German videos?
Hey man, that was really really helpful. Thank you so much for the awesome explanation.
sure
Fantastic video. Beautiful work.
someone get this man a medal
Hey man, thank you for your interview preparation videos. I have got a very good job offer from a startup in India, and your videos played a substantial role in building up my understanding of concepts during interview preparation. Thank you for explaining things so elegantly!
sure, good luck!
Great stuff! Really helped me understand these concepts!
god bless you, i was trying to understand an exercices and just by saying it's like water pipe everything was so clear ! i wasn't thinking i can understand so fast with just a trivial comparaison xD
But anyway thanks ! you're the best :)
Best video i have ever seen thanks a lot.
Thanks that was worth the watch!
Thank you so much, I finally understood what was happening there. I read the book, not only consumes a lot of time but it can be tricky to understand. You helped me finally clearing up any question I had.
Happy Holidays 🎉 Thank you for your kind words, Anto-y! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
Operations Research student here , thanks Ben !
Sure yo
Amazing! My university professor recommended your videos last week in class🤗 Could you also explain when you have time the Bellman Ford algorithm?
Yeah possibly
Which UNIVERSITY?
@@PankajKP LPU
Great video, clearified a lot! Thank you
Hi Ben, Great work! These videos are so helpful for interview preparation. Can you make a video to go over Union-Find data structure ?
Yes I can, just time limits my ability to contribute here.
wow, it's so clear and intuitive. Thanks a lot. It helps me to understand more after diving complicated concepts in textbook.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Well done, that was a big help. Thanks!
That was very helpful, thanks!
Finally an explanation that makes sense to me.
Thank you! Brilliant explanation, so easy and clear!
thanks
Great Explanation
this was amazing
Thank you professor!!!
Thanks! Your video lets me understand the theorem.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Love this! Can you do a video on the dp algorithm for Regular Expression Matching next?
Yeah I can, just time constrained.
"S-T cut, S must be in A and T must be in B" exactly what I was searching for, most memorable. Thanks
thanks for your video it help me to understand maxflow -mincut more directly
nice
Your "undo" gives me the epiphany! Thank you!
You're videos are amazing! Keep it up
ok
This is very good content!
Thanks for explaining this. You have good teaching skills.
Thanks
Really thanks !
good job brother very appreciate it
Thanks man!
thanks, was so much easier to understand after i watched the video
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Great video!
Awesome explanation bro!!! Just Watched till 5:47 but felt amazing man!.
ye
Thanks for nice explanation. Much appreciated.
Happy Holidays 🎉 Thank you for your kind words, Shamanstation! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
I never understood that back edges concept until i saw this one.
thank you so much !
Great job in explaining the reason why the undo operations work!!
sure
Seems like you are going with what is being taught in classes :P
Great video, thanks again.
Yes, I am.
great explanation. no stutter.no bullshit. just good solid well explained!
thank you
thx
Wow really clear and good video! Thanks!
ye
Thanks, Man for the awsome explanation
ye
Please a qustion, can we hav more than one min cut in a network flow? Bcs from what i did i get 2 min cuts cuz when i sum both gives me the max flow value i got.
my man Ben doing God's work! Thank you so much!
hello
Thanks a lot for all your videos. Could you please upload some more videos on greedy problems and about the approach to solve them. for ex the gas station problem in Leetcode.
ok
Thank you!
Thank you. The tutorial is quite helpful.
great.
What. A. Legend.
what a life saver
This is a very good video