filmov
tv
Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)
Показать описание
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
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
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
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
0:21:56
Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)
0:02:24
9 Flow Maximum Flow Minimum cut
0:05:15
Ford-Fulkerson in 5 minutes
0:13:25
Max Flow Ford Fulkerson | Network Flow | Graph Theory
0:10:17
The Maximum Flow Minimum cut Theorem
0:01:49
Flows and Cuts - Georgia Tech - Computability, Complexity, Theory: Algorithms
0:14:02
Maximum flow Minimum Cut Algorithm
0:05:22
The Max Flow Min Cut Theorem: The Ford Fulkerson Algorithm
0:06:59
OCR MEI MwA H: Network Flows: 05 Maximum Flow / Minimum Cut Theorem
0:07:43
lecture network flows 07 max flow min cut theorem
1:22:58
13. Incremental Improvement: Max Flow, Min Cut
0:10:20
Critical Path Analysis Part 3: The Max-Flow/Min- Cut Theorem
0:05:05
OCR MEI MwA H: Network Flows: 04 Introducing Cuts
0:09:05
Ford Fulkerson Algorithm for Maximum Flow Problem
0:07:53
Maximum Flow and Minimum Cut of a Network
0:05:11
Maximum flow problem - Ford Fulkerson algorithm
0:04:59
Finding maximum flow through a network
0:11:53
Introduction to Flow Networks - Tutorial 4 (What is a Cut Min cut problem)
0:10:00
Minimum cuts and maximum flow rate
0:01:44
The Max-Flow Min-Cut Theorem - GT- Computability, Complexity, Theory: Algorithms
0:14:14
CSE 550 (2022, Fall): 3.4 Max-Flow-Min-Cut Theorem
0:13:13
Ford Fulkerson algorithm for Maximum Flow Problem Example
0:10:05
21.3 Network flows
0:10:48
The Maximum Flow Minimum cut Theorem: Part 2
Комментарии