V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Maximum Flow

Find augmenting paths in a residual network, push each bottleneck, and use reverse edges to reroute flow.

Core idea

A residual network records how much more flow can move forward and how much previous flow can be canceled backward. Each augmenting path pushes its smallest residual capacity.

Read the visualization

Edge labels show flow over capacity. The active path is highlighted before its bottleneck is added, and reverse residual choices preserve the ability to reroute earlier decisions.

0/30/30/10/30/3ssourceabtsink

Initialize every network edge with zero flow and its full residual capacity.

1function maxFlow(n: number, edges: [number, number, number][], s: number, t: number): number {
2 const cap = Array.from({ length: n }, () => new Array(n).fill(0));
3 for (const [u, v, c] of edges) cap[u][v] += c; // init amount capacity (init edge init 0)
4 let flow = 0;
5 const dfs = (u: number, pushed: number, vis: boolean[]): number => {
6 if (u === t) return pushed;
7 vis[u] = true;
8 for (let v = 0; v < n; v++) {
9 if (!vis[v] && cap[u][v] > 0) { // augment amount > 0 augment
10 const d = dfs(v, Math.min(pushed, cap[u][v]), vis);
11 if (d > 0) { cap[u][v] -= d; cap[v][u] += d; return d; } // augment flow + augment edge augment amount
12 }
13 }
14 return 0;
15 };
16 for (;;) {
17 const pushed = dfs(s, Infinity, new Array(n).fill(false)); // find one count augmenting path
18 if (pushed === 0) break;
19 flow += pushed; // find bottleneck
20 }
21 return flow;
22}
source → sinks → t
current flow0 / maximum 6
1 / 10

Complexity and tradeoffs

Time: O(EF) for integer Ford-Fulkerson. Space: O(V+E). The bound depends on maximum flow F; Edmonds-Karp or Dinic gives stronger path-selection guarantees.

Invariant: Every intermediate flow respects edge capacities and conserves flow at all vertices except the source and sink.

Where it fits

Maximum flow solves transport capacity, bipartite matching, image segmentation, and many disjoint-path problems. The final unreachable boundary also identifies a minimum cut.