Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm) 

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Flow Networks: en.wikipedia.o...
Ford-Fulkerson Algorithm: en.wikipedia.o...
Max-Flow Min-Cut Theorem: en.wikipedia.o...
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