Hungarian minimum-cost assignment: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Grow an alternating tree, update row/column potentials by minimum slack, then augment the matching when a free column is reached.

Grow an alternating tree from each unmatched worker. Maintain minimum reduced-cost slacks, shift row and column potentials by the smallest slack, and augment through predecessor columns when a free job is reached.

Open the 3D visualization

Hungarian minimum-cost assignment example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Hungarian minimum-cost assignment

Finding a minimum-cost perfect matching between equally sized worker and job sets.

Choosing an alternative

Maximum bipartite matching tests feasibility without minimizing edge cost. This primal-dual assignment solver uses costs and potentials, and produces one optimal distinct-job assignment.

Worked example: input and state changes

Example input

4,1,3;2,0,5;3,2,2

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: Costs with row potentials u, column potentials v, and current slacks.

    State at this checkpoint
    {
      "values": [
        0,
        4,
        1,
        3,
        0,
        2,
        0,
        5,
        0,
        3,
        2,
        2,
        0,
        0,
        0,
        0,
        0,
        "∞",
        "∞",
        "∞"
      ],
      "active": [],
      "kind": "matrix",
      "columns": 4,
      "rowLabels": [
        "worker 0",
        "worker 1",
        "worker 2",
        "column v",
        "slack"
      ],
      "columnLabels": [
        "row u",
        "job 0",
        "job 1",
        "job 2"
      ],
      "result": 0,
      "output": [
        -1,
        -1,
        -1
      ]
    }
  2. Step 2: Augment the matching for worker 0.

    State at this checkpoint
    {
      "values": [
        1,
        4,
        1,
        3,
        0,
        2,
        0,
        5,
        0,
        3,
        2,
        2,
        0,
        0,
        0,
        0,
        0,
        3,
        0,
        2
      ],
      "active": [
        2
      ],
      "kind": "matrix",
      "columns": 4,
      "rowLabels": [
        "worker 0",
        "worker 1",
        "worker 2",
        "column v",
        "slack"
      ],
      "columnLabels": [
        "row u",
        "job 0",
        "job 1",
        "job 2"
      ],
      "result": 0,
      "output": [
        1,
        -1,
        -1
      ]
    }
  3. Step 4: Adjust potentials by minimum slack 2; inspect job 0.

    State at this checkpoint
    {
      "values": [
        3,
        4,
        1,
        3,
        2,
        2,
        0,
        5,
        0,
        3,
        2,
        2,
        0,
        0,
        -2,
        0,
        0,
        0,
        0,
        0
      ],
      "active": [
        1
      ],
      "kind": "matrix",
      "columns": 4,
      "rowLabels": [
        "worker 0",
        "worker 1",
        "worker 2",
        "column v",
        "slack"
      ],
      "columnLabels": [
        "row u",
        "job 0",
        "job 1",
        "job 2"
      ],
      "result": 0,
      "output": [
        1,
        -1,
        -1
      ]
    }
  4. Step 6: Adjust potentials by minimum slack 2; inspect job 2.

    State at this checkpoint
    {
      "values": [
        3,
        4,
        1,
        3,
        2,
        2,
        0,
        5,
        2,
        3,
        2,
        2,
        0,
        0,
        -2,
        0,
        0,
        1,
        2,
        0
      ],
      "active": [
        11
      ],
      "kind": "matrix",
      "columns": 4,
      "rowLabels": [
        "worker 0",
        "worker 1",
        "worker 2",
        "column v",
        "slack"
      ],
      "columnLabels": [
        "row u",
        "job 0",
        "job 1",
        "job 2"
      ],
      "result": 0,
      "output": [
        1,
        0,
        -1
      ]
    }
  5. Step 8: Minimum assignment cost 5.

    State at this checkpoint
    {
      "values": [
        3,
        4,
        1,
        3,
        2,
        2,
        0,
        5,
        2,
        3,
        2,
        2,
        0,
        0,
        -2,
        0,
        0,
        1,
        2,
        0
      ],
      "active": [
        2,
        5,
        11
      ],
      "kind": "matrix",
      "columns": 4,
      "rowLabels": [
        "worker 0",
        "worker 1",
        "worker 2",
        "column v",
        "slack"
      ],
      "columnLabels": [
        "row u",
        "job 0",
        "job 1",
        "job 2"
      ],
      "result": 5,
      "output": [
        1,
        0,
        2
      ]
    }

Expected final state

Minimum assignment cost 5.

Complexity and input bounds

Family: Optimization. Time complexity: O(n^3).

Implementation detail: Square matrices have at most five rows and costs 0..99. The view shows costs, row/column potentials and slacks. Downloads return minimum cost and write zero-based job indices per worker. This is the cubic shortest-augmenting-path formulation, with deterministic first-predecessor tie handling. All matrix entries are available assignments.

Space complexity: O(n) potentials, predecessor and matching arrays, excluding the n by n input matrix and saved frames.

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.

Square 1..5 cost matrix, rows separated by ;. Costs 0..99. Every worker receives a distinct job.

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

Keep dummy column zero separate from real jobs. Update potentials only for visited columns and subtract the shift from other slacks. Several optimal assignments can exist when costs tie.

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
// Square row-major cost matrix n 0..5, costs 0..99, output capacity n. Returns minimum assignment cost and writes zero-based job index per worker, with distinct jobs. Empty matrix returns 0. Uses one-based row/column potentials, minimum slack and shortest alternating augmentations; ties retain first predecessor and smallest scanned column. Multiple optimal assignments may exist. O(n^3) time and O(n) scratch excluding input/output. All entries are available edges; forbidden assignments are not supported. 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(costs, n, output) {
    let u = Array(256).fill(0); let v = Array(256).fill(0); let p = Array(256).fill(0); let way = Array(256).fill(0); let minv = Array(256).fill(0); let used = Array(256).fill(0); let column = 0; let row = 0; let delta = 0; let nextColumn = 0; let reduced = 0; let previous = 0;
    for (let worker = 1; worker <= n; worker++) { p[0] = worker; column = 0; for (let j = 0; j <= n; j++) { minv[j] = 1000000; used[j] = 0; }
     while (p[column] != 0) { used[column] = 1; row = p[column]; delta = 1000000; nextColumn = 0;
      for (let j = 1; j <= n; j++) { if (used[j] == 0) { reduced = costs[(row-1)*n+j-1]-u[row]-v[j]; if (reduced < minv[j]) { minv[j] = reduced; way[j] = column; } if (minv[j] < delta) { delta = minv[j]; nextColumn = j; } } }
      for (let j = 0; j <= n; j++) { if (used[j] != 0) { u[p[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; } } column = nextColumn;
     }
     while (column != 0) { previous = way[column]; p[column] = p[previous]; column = previous; }
    }
    for (let j = 1; j <= n; j++) { output[p[j]-1] = j-1; }
    return 0-v[0];
}

Source

Kuhn is the foundational Hungarian-method paper. The playground uses the later cubic primal-dual shortest-augmenting-path formulation explained by the authored implementation reference.