Sometimes it is also because at this point you already have some idea of algorithm and understand some of its key concepts, so when William teaches you this you have an easier time grasping it.
Oh! My god! I'm reading the famours book: "computational complexity", No matter how many times I've read the text about the "MAXIMUM FLOW" section, I couldn't understand it, until I found this video. Now I suspect those professors were trying to make the knowledge as difficult as possible in order to protect their power. Even I could fully understand this problem now, when I re-read the text about the "maximum flow" in this book, I still don't know what they are talking about.
I wonder why this video is not highlighted in the search results. This is a wonderful video with effective teaching. You have done a good job William. Please Keep it going for lot more people to benefit!
Good video, but there's a few things that could be improved. Residual edge is incorrectly defined at 6:00. At 4:20 he says you're probably wondering what a residual graph is, and then he proceeds to use the word residual before defining it! In Ford-Fulkerson, we assume each edge has an edge in the opposite direction. Where the capacity is only given in 1 direction, set the other direction's capacity to 0. Assign a flow of 0 to each edge, and then as the algorithm proceeds, the flow on each edge can be changed. But when you change the flow of an edge to x, you MUST assign -x to the flow in the opposite direction. This is NOT called a "residual". The residual exists in both directions. The residual (which means "quantity remaining") of an edge is what at 7:29 he calls "remaining capacity". It is simply the capacity of the edge minus the current flow. i.e. If the residual is > 0, there is still room for more flow. The residual graph is just the whole set of residual edges. The word saturate in general can mean "fill until no more can be held". In this case, a saturated edge has residual == 0.
Thank you so much. I am struggling with this so much. Would you have a book or website that could explain this in a completely clear way. I still struggled with this video.
@@marfa_rfa I think the Wikipedia page on Ford-Fulkerson gives a pretty nice overview, although it does use some very mathsy notation. I'm sure there are other great resources out there, maybe lecture notes, but I don't know of any myself, sorry.
Best explanation!! I watched some videos but this one was really in detail, giving examples and again repeating what a risidual network acually is, how capacities work and the principle of augmenting paths. Thanks a bunch my assignment was even fun when I understood it thanks to you~
Amazing explanation and I love the animation as well! I think it is worth pointing out that the key observation that the sum of the bottlenecks (found in each augmenting path) equals the max flow is only true because we assumed the initial arc flow is 0 for each arc. If we do not assume this, then you need to add the initial value of the flow (of the graph) to the sum of bottlenecks as well.
Thanks William, that was the best video i have seen for Residual Graphs and Augmenting paths, and trust me i saw many. You managed to make me undestand what my professor's couldn't in 100 silides.
I got totally lost around 4:47 when he starts talking about edges being saturated...? And what is a residual graph? And I don't remember depth first search... What if there are two bottlenecks in the graph?
Good video, but there's a few things that could be improved. Residual edge is incorrectly defined at 6:00. At 4:20 he says you're probably wondering what a residual graph is, and then he proceeds to use the word residual before defining it! In Ford-Fulkerson, we assume each edge has an edge in the opposite direction. Where the capacity is only given in 1 direction, set the other direction's capacity to 0. Assign a flow of 0 to each edge, and then as the algorithm proceeds, the flow on each edge can be changed. But when you change the flow of an edge to x, you MUST assign -x to the flow in the opposite direction. This is NOT called a "residual". The residual exists in both directions. The residual (which means "quantity remaining") of an edge is what at 7:29 he calls "remaining capacity". It is simply the capacity of the edge minus the current flow. i.e. If the residual is > 0, there is still room for more flow. The residual graph is just the whole set of residual edges. The word saturate in general can mean "fill until no more can be held". In this case, a saturated edge has residual == 0.
If Timotheus' pole has a network flow capacity of 8 units spunk along its edge, delta net, how much bottleneck maximum flow can Timotheus' hole take before it fissures?
Maybe when people learn theses concepts by themselves rather than being forced by the college it will be easier for them to understand. Anyway this video is awesome. Brief and clear. Thank you so much.
Is there a particular reason why the "maximum flow" calculated using the "sum of bottleneck values"? Instead of using the "sum of outflow from the source node"? I found the "sum of outflow from the source node" easier to interpret, that's all.
The bottleneck approach is more useful to understand min-cut. Looking at the capacities that are actually filled gives you more information on how to reconstruct the optimal answer than looking at the outflow from the source. Sometimes, designing network flows is also easier to come about if you think about it in terms of min-cut.
I have a doubt: why we have to compute the augmenting path (s -> 0 -> 3 -> t), if the arrow goes from 3 to 0 (3 -> 0), and not from 0 to 3 (0 -> 3)? Thanks.
Can you please teach the same thing to our professor who is teaching us the network flow. He is trying to explain the same thing to us from last 3 lectures and out of 250 not even 25 of us is able to understand the same.
There is a lot good work in this video. At least give a hint on what is not clear to you. I think if you have your display and sound on, it is easy to follow and well explained
Watching this in 2023 for my exam in Algorithm and Datastructures, love the explanation
where do you study bro ?
In so sure hes also German haha @@Iam_number_one
I would thank my professor explaining the algorithm so terriblely otherwise I won't find this awesome channel!
You spent less time than my Prof to explain this and you nailed it. Awesome!
My prof is so old and senile I swear to God he was out there helping Alan Turing crack the enigma back in the day
@@yoavmor9002 lol
Sometimes it is also because at this point you already have some idea of algorithm and understand some of its key concepts, so when William teaches you this you have an easier time grasping it.
Oh! My god! I'm reading the famours book: "computational complexity", No matter how many times I've read the text about the "MAXIMUM FLOW" section, I couldn't understand it, until I found this video.
Now I suspect those professors were trying to make the knowledge as difficult as possible in order to protect their power. Even I could fully understand this problem now, when I re-read the text about the "maximum flow" in this book, I still don't know what they are talking about.
I wonder why this video is not highlighted in the search results. This is a wonderful video with effective teaching. You have done a good job William. Please Keep it going for lot more people to benefit!
Good video, but there's a few things that could be improved.
Residual edge is incorrectly defined at 6:00. At 4:20 he says you're probably wondering what a residual graph is, and then he proceeds to use the word residual before defining it!
In Ford-Fulkerson, we assume each edge has an edge in the opposite direction. Where the capacity is only given in 1 direction, set the other direction's capacity to 0.
Assign a flow of 0 to each edge, and then as the algorithm proceeds, the flow on each edge can be changed. But when you change the flow of an edge to x, you MUST assign -x to the flow in the opposite direction. This is NOT called a "residual". The residual exists in both directions.
The residual (which means "quantity remaining") of an edge is what at 7:29 he calls "remaining capacity".
It is simply the capacity of the edge minus the current flow. i.e. If the residual is > 0, there is still room for more flow. The residual graph is just the whole set of residual edges.
The word saturate in general can mean "fill until no more can be held". In this case, a saturated edge has residual == 0.
thank you!
Thank you so much. I am struggling with this so much. Would you have a book or website that could explain this in a completely clear way. I still struggled with this video.
@@marfa_rfa I think the Wikipedia page on Ford-Fulkerson gives a pretty nice overview, although it does use some very mathsy notation. I'm sure there are other great resources out there, maybe lecture notes, but I don't know of any myself, sorry.
My thoughts when I first saw this algorithm 4:17 - 4:23
Literally said it out-loud in zoom class last week ... accidentally.
@Archer Grayson lmao u really made two accounts for this
This is the best algorithm channel on youtube, thank you for this video.
Only video that explains the concepts clearly without confusing the mess out of you🤣
Watching this in 2024 for my exam in Algorithms, love the explanation
Best explanation!! I watched some videos but this one was really in detail, giving examples and again repeating what a risidual network acually is, how capacities work and the principle of augmenting paths. Thanks a bunch my assignment was even fun when I understood it thanks to you~
Amazing as always !! The impact these videos will have over time will be phenomenal ... Let my comment bear testimony to that prediction ...
Thank you!
Agreed
Love your network flow playlist, getting ready to watch it all again for the 2nd time. Great videos :D
Best series on youtube yet
Thanks William, your videos have already helped to get Tarjan's algorithm and this video is super clear, as well! ;-)
this is so clear. my professors explanation was over an hour & made no sense. and you didn't oversimplify either! cheers
Really well done! Best video for Max flow i have seen so far!
Amazing explanation and I love the animation as well! I think it is worth pointing out that the key observation that the sum of the bottlenecks (found in each augmenting path) equals the max flow is only true because we assumed the initial arc flow is 0 for each arc. If we do not assume this, then you need to add the initial value of the flow (of the graph) to the sum of bottlenecks as well.
i have an exam in an hour , i just love u
Your explanation is so clear! Also, I love the illustrations. Keep up the good work!
Thanks William, that was the best video i have seen for Residual Graphs and Augmenting paths, and trust me i saw many. You managed to make me undestand what my professor's couldn't in 100 silides.
This is so awesome!! Thank you! How come people dislike it?? 18 university prof?
someone give this man a GOLD......wait this isn't reddit
Great work on this! One of the clearest explanations I have seen
Can you make one video on Push-Relabel algorithm also?
Very nice explanation
Very clear
I love this so much
Thank you so much for this!
very good and clear video! I can now understand what is going on in the reverse operation!
But what is a residual graph? You went straight to augmenting path.
I got totally lost around 4:47 when he starts talking about edges being saturated...? And what is a residual graph? And I don't remember depth first search... What if there are two bottlenecks in the graph?
Good video, but there's a few things that could be improved.
Residual edge is incorrectly defined at 6:00. At 4:20 he says you're probably wondering what a residual graph is, and then he proceeds to use the word residual before defining it!
In Ford-Fulkerson, we assume each edge has an edge in the opposite direction. Where the capacity is only given in 1 direction, set the other direction's capacity to 0.
Assign a flow of 0 to each edge, and then as the algorithm proceeds, the flow on each edge can be changed. But when you change the flow of an edge to x, you MUST assign -x to the flow in the opposite direction. This is NOT called a "residual". The residual exists in both directions.
The residual (which means "quantity remaining") of an edge is what at 7:29 he calls "remaining capacity".
It is simply the capacity of the edge minus the current flow. i.e. If the residual is > 0, there is still room for more flow. The residual graph is just the whole set of residual edges.
The word saturate in general can mean "fill until no more can be held". In this case, a saturated edge has residual == 0.
wached 3 videos before that didn't help me, I'm glad you did
This is beautiful, thank you so much!
Residual edges is more like an undo
In augmenting paths, we can only select the path whose remaining capacity is greater than zero
Great Explanation
Appreciate the videos! I'm in an operations research course and it's hard finding clips on some of these algorithms!
If Timotheus' pole has a network flow capacity of 8 units spunk along its edge, delta net, how much bottleneck maximum flow can Timotheus' hole take before it fissures?
love your stuff, now I need to rewatch it to sink it xd
Maybe when people learn theses concepts by themselves rather than being forced by the college it will be easier for them to understand. Anyway this video is awesome. Brief and clear. Thank you so much.
Great explanation!
Thank you for your helpful explanation!!!
Awesome introduction, thanks!
Awesome video man, life-saving. Very well explained
Best explanation. Thanks!
how did the 4th/last augmented path had bottleneck value - 6?
At 2:42, the max flow is 7. But I am not able to get any min-cut of value 7, the least I cab generate is 8. Can anyone find a mincut?
teacher thanks. Muchas gracias con lo poco que entiendo ingles me ayudaste gracias profe.
Could you explain how you came at 2/100 at 11:15 ?
damn now I understand it, my professor f.. failed to teach it at least to me
Is there a particular reason why the "maximum flow" calculated using the "sum of bottleneck values"? Instead of using the "sum of outflow from the source node"?
I found the "sum of outflow from the source node" easier to interpret, that's all.
The bottleneck approach is more useful to understand min-cut. Looking at the capacities that are actually filled gives you more information on how to reconstruct the optimal answer than looking at the outflow from the source. Sometimes, designing network flows is also easier to come about if you think about it in terms of min-cut.
Not for someone who's trying to understand this for the first time. If one already knows, animations are nice.
does dfs really choose edges in random order
10:48 Why random?
I have a doubt: why we have to compute the augmenting path (s -> 0 -> 3 -> t), if the arrow goes from 3 to 0 (3 -> 0), and not from 0 to 3 (0 -> 3)? Thanks.
He said at ( 9:09 )that we can use the residual edge, we have created. So basically we used the residual edge 0->3
@@ahlahous8128 Thanks!
From what time the F-F algo actually starts on example?
What about push relabel. Its not in the playlist!!
Can you please make videon busacker and gowen method for network flow
Very useful. Makes good sense! :D
which tool do u use for animation ?
Thanks mate appreciate it
Thank you.
great explanation. thanks for the video and quality explanation with the visualizations!
thank you
You are the guy from data structures crash course by freecodecamp right??
if it weren't for youtube, i wouldn't be graduating college
You sound a bit like Ross Geller from time to time lol! Great material tho, much appreciated hah!
Thanks!
great video! keep it up :D
thanks sir 😊
Algorithme Ford-Fulkerson (Flot maximal) Méthode marquage
th-cam.com/video/YnKXJAxUAu4/w-d-xo.html
was this video supposed to be revision or first time learning? bc if it was for learning it was terrible cant lie
What is missing? Anything I can clarify?
@@WilliamFiset-videos you skimmed past probably the most confusing part of all of this: residual flow
Can you please teach the same thing to our professor who is teaching us the network flow. He is trying to explain the same thing to us from last 3 lectures and out of 250 not even 25 of us is able to understand the same.
kaunsa clg me padhte ho bhai
He took an augmenting path and augmented all over the place
we miss one or 2. checkout hieros gamos..
poor explanation ! make an example and solve it instead of bla bla
Too fast !!!!I could not understand any word !!!! Your graph is very clear but too much detailed and confusing too much talking and poor explaining
8:08 😑😑
One simple example is asking too much, I suppose. Keep it simple and add complexity, not the inverse. Maybe next time.
#Excelent!
13:25
Why not just do the opposite of a shortest path algorithm? wouldn't that give the maximum flow?
Worst Explanation
Terrible explanation
I WANNA KISS THIS MAN HOLY FUCK THIS SAVED ME A LOT OF TIME
i dont understand shit
Great video, shitty algorithm
Hold on....isn’t this the guy from 3b1b?
εσπασες μας
r u angel ?
Useless explanation
i now understand it less after watching, f***....
i dont get it dude you explain too fast cant keep up disliked
makes no sense
voice is copy of bill gates
terrible explanation, not clear at all
There is a lot good work in this video. At least give a hint on what is not clear to you. I think if you have your display and sound on, it is easy to follow and well explained
Good try but wrong information in some parts.
thank you
11:34