Ford-Fulkerson (DFS) maximum flow: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Ford-Fulkerson (DFS) maximum flow example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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
    }
  2. 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
    }
  3. 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
    }
  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
    }
  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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.