Max Flow Ford Fulkerson | Network Flow | Graph Theory

Показать описание

Explanation of how to find the maximum flow with the Ford-Fulkerson method

Algorithms repository:

Video slides:

0:00 Intro and motivation for maximum flow
2:42 Basics and definitions of network flow concepts
4:26 Augmenting paths, residual edges and the residual graph
8:05 Ford-Fulkerson with DFS example
9:49 Ford-Fulkerson time complexity
11:22 Faster network flow algorithms

======================================

Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on YouTube:

Рекомендации по теме

Комментарии

Watching this in 2023 for my exam in Algorithm and Datastructures, love the explanation

sixtenmuller

You spent less time than my Prof to explain this and you nailed it. Awesome!

sovathanaheng

My thoughts when I first saw this algorithm 4:17 - 4:23

harshitshukla

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.

ZantierTasa

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!

famefurqan

I would thank my professor explaining the algorithm so terriblely otherwise I won't find this awesome channel!

siuhangchen

This is the best algorithm channel on youtube, thank you for this video.

hidayatkhan

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.

salmanfariss

someone give this man a this isn't reddit

mere_illusion

Amazing as always !! The impact these videos will have over time will be phenomenal ... Let my comment bear testimony to that prediction ...

vnnyboy

Only video that explains the concepts clearly without confusing the mess out of you🤣

elisabethwaldron

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~

makii