Published by Dimitris Kougioumtzis · Updated
Choose residual augmenting paths with depth-first search. Integer capacities; source 0, sink highest vertex; parallel capacities are added.
Find an augmenting path by DFS in the residual network. Send its bottleneck capacity and update reverse arcs so later paths can undo earlier routing choices. Repeat until the sink is unreachable.
When to use Ford-Fulkerson (DFS) maximum flow
Small integral-capacity allocation and network throughput models; teaching the maximum-flow minimum-cut relationship.
Choosing an alternative
Edmonds-Karp uses BFS paths and has a capacity-independent polynomial bound; DFS Ford-Fulkerson depends on the integral maximum flow.
Worked example: input and state changes
Example input
0,1,3;0,2,2;1,2,2;1,3,2;2,3,3
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial residual capacities; reverse arcs allow earlier choices to be undone.
State at this checkpoint
{ "values": [ 0, 3, 2, 0, 0, 0, 2, 2, 0, 0, 0, 3, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 4 }Step 1: Augment 0 > 1 > 2 > 3 by 2; total flow 2.
State at this checkpoint
{ "values": [ 0, 1, 2, 0, 2, 0, 0, 2, 0, 2, 0, 1, 0, 0, 2, 0 ], "active": [ 1, 4, 6, 9, 11, 14 ], "kind": "matrix", "columns": 4, "path": [ 0, 1, 2, 3 ], "amount": 2, "result": 2 }Step 3: Augment 0 > 2 > 1 > 3 by 1; total flow 4.
State at this checkpoint
{ "values": [ 0, 0, 1, 0, 3, 0, 1, 0, 1, 1, 0, 1, 0, 2, 2, 0 ], "active": [ 2, 8, 9, 6, 7, 13 ], "kind": "matrix", "columns": 4, "path": [ 0, 2, 1, 3 ], "amount": 1, "result": 4 }Step 4: Augment 0 > 2 > 3 by 1; total flow 5.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 3, 0, 1, 0, 2, 1, 0, 0, 0, 2, 3, 0 ], "active": [ 2, 8, 11, 14 ], "kind": "matrix", "columns": 4, "path": [ 0, 2, 3 ], "amount": 1, "result": 5 }Step 5: Maximum flow = 5. No augmenting path remains.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 3, 0, 1, 0, 2, 1, 0, 0, 0, 2, 3, 0 ], "active": [], "kind": "matrix", "columns": 4, "result": 5, "final": true }
Expected final state
Maximum flow = 5. No augmenting path remains.
Complexity and input bounds
Family: Graphs. Time complexity: O(V^2 * F).
Implementation detail: Dense-matrix DFS costs O(V^2) per augmentation; integral capacities give O(V^2 * F) augmentation work for positive maximum flow F, plus initialization. Downloads return maximum flow and write the final row-major residual matrix. The UI records at most 500 intermediate snapshots followed by the exact final state.
Space complexity: O(V^2) auxiliary space for a dense residual matrix and O(V) search state; recorded frames use additional space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0. Weights are capacities; source 0; sink highest vertex.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Reverse residual capacities are essential. Parallel capacities must be added. Source is vertex 0 and sink is the highest numbered vertex; source equal to sink returns zero. Do not use irrational capacities with the DFS termination argument.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // Directed integer-capacity network, 1..8 vertices, 0..16 edges, capacities 0..99; endpoints in range. Source 0, sink vertices-1. Parallel capacities are summed; antiparallel edges and self-loops are allowed. Output capacity at least vertices*vertices; writes final residual matrix in row-major order and returns maximum flow (0 when source equals sink). Ford-Fulkerson uses DFS paths; O(V^2 * F) time for positive integral maximum flow F, plus initialization. O(V^2) auxiliary space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { let residual = Array(256).fill(0); let level = Array(256).fill(0); let next = Array(256).fill(0); let seen = Array(256).fill(0); let stack = Array(256).fill(0); let flow = 0; let sent = 0; let depth = 0; let u = 0; let v = 0; let amount = 0; for (let i = 0; i < edges; i++) { residual[from[i] * vertices + to[i]] += weight[i]; } while (vertices > 1) { for (let i = 0; i < vertices; i++) { level[i] = -1; next[i] = 0; } sent = 0; while (1 == 1) { for (let i = 0; i < vertices; i++) { seen[i] = 0; next[i] = 0; } depth = 1; stack[0] = 0; seen[0] = 1; while (depth > 0 && stack[depth - 1] != vertices - 1) { u = stack[depth - 1]; v = next[u]; while (v < vertices && (residual[u * vertices + v] <= 0 || seen[v] != 0)) { v++; } next[u] = v; if (v == vertices) { depth--; } else { seen[v] = 1; stack[depth++] = v; } } if (depth == 0) { break; } amount = 1000000; for (let i = 1; i < depth; i++) { u = stack[i - 1]; v = stack[i]; if (residual[u * vertices + v] < amount) { amount = residual[u * vertices + v]; } } for (let i = 1; i < depth; i++) { u = stack[i - 1]; v = stack[i]; residual[u * vertices + v] -= amount; residual[v * vertices + u] += amount; } flow += amount; sent += amount; } if (sent == 0) { break; } break; } for (let i = 0; i < vertices * vertices; i++) { output[i] = residual[i]; } return flow; } |
Source
Original maximum-flow and minimum-cut research. DFS is the playground’s augmenting-path selection rule; the method itself permits different path choices.
- Maximal Flow Through a Network
L. R. Ford, Jr.; D. R. Fulkerson (1956). Research paper.