Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm) @BackToBackSWE
Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)  @BackToBackSWE
Uploaded October 2019 | Updated November 2026, 3 hours ago
Try Our Full Platform: nas.io/backtobackswe
๐Ÿ“น Intuitive Video Explanations
โ“New Unseen Questions
๐Ÿ”Ž Get All Solutions

Flow Networks: en.wikipedia.org/wiki/Flow_network
Fordโ€“Fulkerson Algorithm: en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Max-Flow Min-Cut Theorem: 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|)).


#backtobackswe #benyamephrem
Network Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)Coding Interview | Terms to know | API & ADT  #shorts #datastructures #codinginterviewMerge K Sorted Arrays - Min Heap Algorithm (Merge K Sorted Lists on LeetCode)Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions4 Tips To Learn Java Programming As Fast As Possible As A BeginnerProfessor Clyde Kruskal On Kruskals AlgorithmPartition To K Equal Sum Subsets From An Array of Integers - The Backtracking ApproachAdd Two Numbers Without The + Sign (Bit Shifting Basics)Compute The Next Permutation of A Numeric Sequence - Case Analysis (Next Permutation on Leetcode)Serialize & Deserialize A Binary Tree - Crafting Recursive Solutions To Interview ProblemsGenerate All Strings With n Matched Parentheses - Backtracking (Generate Parentheses on LeetCode)
Back To Back SWE |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER