Ford-Fulkerson Max Flow
Compute maximum flow in network from source to sink. Ford-Fulkerson method finds augmenting paths until none exist. Edmonds-Karp implementation uses BFS for O(VE²) complexity. Fundamental algorithm in network optimization, matching problems, and resource allocation.
Visualization
Interactive visualization for Ford-Fulkerson Max Flow
Edges (capacity / flow):
- 0 → 1: 0 / 10
- 0 → 2: 0 / 5
- 1 → 2: 0 / 15
- 1 → 3: 0 / 10
- 2 → 3: 0 / 10
Interactive visualization with step-by-step execution
Implementation
1function fordFulkerson(graph: number[][], source: number, sink: number): number {
2 const n = graph.length;
3 const residual = graph.map(row => [...row]);
4 let maxFlow = 0;
5
6 function bfs(): number[] | null {
7 const visited = new Array(n).fill(false);
8 const parent = new Array(n).fill(-1);
9 const queue = [source];
10 visited[source] = true;
11
12 while (queue.length > 0) {
13 const u = queue.shift()!;
14
15 for (let v = 0; v < n; v++) {
16 if (!visited[v] && residual[u][v] > 0) {
17 visited[v] = true;
18 parent[v] = u;
19 queue.push(v);
20
21 if (v === sink) return parent;
22 }
23 }
24 }
25 return null;
26 }
27
28 let parent: number[] | null;
29 while ((parent = bfs()) !== null) {
30 let pathFlow = Infinity;
31
32 for (let v = sink; v !== source; v = parent[v]) {
33 const u = parent[v];
34 pathFlow = Math.min(pathFlow, residual[u][v]);
35 }
36
37 for (let v = sink; v !== source; v = parent[v]) {
38 const u = parent[v];
39 residual[u][v] -= pathFlow;
40 residual[v][u] += pathFlow;
41 }
42
43 maxFlow += pathFlow;
44 }
45
46 return maxFlow;
47}Deep Dive
Theoretical Foundation
Ford-Fulkerson method computes maximum flow in a flow network by finding augmenting paths from source to sink and pushing flow along them until no more paths exist. The algorithm maintains a residual graph showing remaining capacity on each edge. For each augmenting path found, it determines the bottleneck (minimum capacity along path) and augments flow by this amount. The residual graph is updated: forward edges decrease by flow amount, backward edges increase (allowing flow reversal). Edmonds-Karp uses BFS to find shortest augmenting paths, guaranteeing O(VE²) time. The Max-Flow Min-Cut theorem states that maximum flow equals minimum cut capacity.
Complexity
Time
O(VE²) with BFS
O(VE²)
O(E×max_flow)
Space
O(V²)
Applications
Industry Use
Network routing and bandwidth allocation
Bipartite matching (marriage problem, job assignment)
Supply chain optimization
Image segmentation (min-cut for foreground/background)
Airline crew scheduling
Traffic flow optimization in transportation
Resource allocation in project management
Circulation problems in logistics
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.