Published by Dimitris Kougioumtzis · Updated
Build BFS levels and send a blocking flow using current-arc DFS. Integer capacities; source 0, sink highest vertex; parallel capacities are added.
Build shortest-path levels with BFS, then repeatedly send flow through level-respecting DFS paths until the level network is blocked. Current-arc cursors avoid rescanning exhausted neighbors within a phase.
When to use Dinic maximum flow
Small integral-capacity allocation and network throughput models; teaching the maximum-flow minimum-cut relationship.
Choosing an alternative
Edmonds-Karp augments along one shortest residual path per BFS; Dinic sends a complete blocking flow per BFS phase.
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 2: Augment 0 > 1 > 3 by 2; total flow 2.
State at this checkpoint
{ "values": [ 0, 1, 2, 0, 2, 0, 2, 0, 0, 0, 0, 3, 0, 2, 0, 0 ], "active": [ 1, 4, 7, 13 ], "kind": "matrix", "columns": 4, "path": [ 0, 1, 3 ], "amount": 2, "result": 2 }Step 4: BFS levels: 0, 1, 2, 3.
State at this checkpoint
{ "values": [ 0, 1, 0, 0, 2, 0, 2, 0, 2, 0, 0, 1, 0, 2, 2, 0 ], "active": [], "kind": "matrix", "columns": 4, "level": [ 0, 1, 2, 3 ] }Step 5: Augment 0 > 1 > 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": [ 1, 4, 6, 9, 11, 14 ], "kind": "matrix", "columns": 4, "path": [ 0, 1, 2, 3 ], "amount": 1, "result": 5 }Step 7: 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 * (V + E)).
Implementation detail: The dense-matrix current-arc version takes O(V^2 * (V + E)) time; adjacency-list Dinic has the usual O(V^2 * E) bound. 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 33 34 35 36 37 38 39 | // 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). Dinic uses BFS levels and current-arc DFS blocking flows. Dense residual scans give O(V^2 * (V+E)) time. 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 queue = Array(256).fill(0); let head = 0; let tail = 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; } head = 0; tail = 1; queue[0] = 0; level[0] = 0; while (head < tail) { u = queue[head++]; for (v = 0; v < vertices; v++) { if (residual[u * vertices + v] > 0 && level[v] < 0) { level[v] = level[u] + 1; queue[tail++] = v; } } } if (level[vertices - 1] < 0) { break; } sent = 0; while (1 == 1) { for (let i = 0; i < vertices; i++) { seen[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 || level[v] != level[u] + 1)) { v++; } next[u] = v; if (v == vertices) { level[u] = -1; 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; } } for (let i = 0; i < vertices * vertices; i++) { output[i] = residual[i]; } return flow; } |
Source
Original 1970 publication for layered maximum flow. The playground uses the later current-arc DFS blocking-flow formulation, rather than reproducing the paper’s original program.
- An algorithm for the solution of the problem of maximal flow in a network with power estimation
Y. A. Dinitz (1970). Original research paper (Russian).