Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Flow Networks: https://en.wikipedia.org/wiki/Flow_network
Ford–Fulkerson Algorithm: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Max-Flow Min-Cut Theorem: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
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|)).
Видео Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm) канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Flow Networks: https://en.wikipedia.org/wiki/Flow_network
Ford–Fulkerson Algorithm: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Max-Flow Min-Cut Theorem: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
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|)).
Видео Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm) канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![Ford-Fulkerson in 5 minutes — Step by step example](https://i.ytimg.com/vi/Tl90tNtKvxs/default.jpg)
![DM 01 Max Flow and Min Cut Theorem Transport Network Flow Example Solution](https://i.ytimg.com/vi/a0XlX0NwRhM/default.jpg)
![How I Got An Internship @ Twitter](https://i.ytimg.com/vi/DUqwi-uUzWs/default.jpg)
![](https://i.ytimg.com/vi/7yC1aN87Ydo/default.jpg)
![Max Flow Ford Fulkerson | Network Flow | Graph Theory](https://i.ytimg.com/vi/LdOnanfc5TM/default.jpg)
![13. Incremental Improvement: Max Flow, Min Cut](https://i.ytimg.com/vi/VYZGlgzr_As/default.jpg)
![8. NP-Hard and NP-Complete Problems](https://i.ytimg.com/vi/e2cF8a5aAhE/default.jpg)
![Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation](https://i.ytimg.com/vi/RGuJga2Gl_k/default.jpg)
![3.5 Prims and Kruskals Algorithms - Greedy Method](https://i.ytimg.com/vi/4ZlRH0eK-qQ/default.jpg)
![Find the k'th Largest or Smallest Element: From Sorting To Heaps To Partitioning](https://i.ytimg.com/vi/hGK_5n81drs/default.jpg)
![4.4 Bellman Ford Algorithm - Single Source Shortest Path - Dynamic Programming](https://i.ytimg.com/vi/FtN3BYH2Zes/default.jpg)
![Ford Fulkerson Algorithm Edmonds Karp Algorithm For Max Flow](https://i.ytimg.com/vi/GiN3jRdgxU4/default.jpg)
![Algorithms Course - Graph Theory Tutorial from a Google Engineer](https://i.ytimg.com/vi/09_LlHjoEiY/default.jpg)
![Edmonds Karp Algorithm | Network Flow | Graph Theory](https://i.ytimg.com/vi/RppuJYwlcI8/default.jpg)
![The Maximum Flow Minimum cut Theorem](https://i.ytimg.com/vi/wQG-sdtmhVQ/default.jpg)
![The Four Color Theorem | Coloring a Planar Graph](https://i.ytimg.com/vi/42-ws3bkrKM/default.jpg)
![Search A 2D Sorted Matrix - Fundamentals of Search Space Reduction](https://i.ytimg.com/vi/FOa55B9Ikfg/default.jpg)
![Ford-Fulkerson Algorithm](https://i.ytimg.com/vi/v1VgJmkEJW0/default.jpg)
![Lec-40 Ford Fulkerson Algorithm For Max Flow | Hindi | Operation Research](https://i.ytimg.com/vi/NwenwITjMys/default.jpg)
![Unweighted Bipartite Matching | Network Flow | Graph Theory](https://i.ytimg.com/vi/GhjwOiJ4SqU/default.jpg)