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.
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.
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 ] }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 ] }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 ] }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 ] }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:
- 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 | // 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.
- The Hungarian method for the assignment problem
Harold W. Kuhn (1955). Foundational Hungarian-method research. - Hungarian algorithm for solving the assignment problem
CP-Algorithms contributors (2026). Authored cubic implementation explanation.