Bipartite Matching answers "how many pairs" — every edge either exists or doesn't, and the only question is the largest conflict-free set of them. The Hungarian Algorithm (also called Kuhn–Munkres) answers a different, harder question about the same shape of graph: every edge carries a cost, and the goal is the cheapest way to match every worker to exactly one job, not just the largest matching. This is the classic assignment problem, and it's the exact gap Bipartite Matching's own Pitfalls section named and left open: "max flow only ever counts units, it has no notion of an edge being preferable to another edge of the same capacity... the Hungarian method solves weighted bipartite matching directly; not built on this site." This is that page, fifth Network Flow entry and the first where the graph carries real numbers instead of just existing or not.
The trick isn't a different search — it's making a weighted problem answerable by the same kind of
unweighted alternating-path search Bipartite Matching already used. Give every worker a number ui
and every job a number vj (potentials), chosen so ui +
vj ≤ costij always holds. Call an edge tight when that inequality is
an equality. Restrict the search to only tight edges — the equality subgraph — and run Kuhn's
algorithm (unweighted augmenting-path matching) inside it. When the search gets stuck, don't give up: adjust the
potentials by the smallest amount that makes at least one new edge tight, and try again. See Why below for why
this always converges to the cheapest assignment, never just a locally decent one.
Three workers, three jobs, a fixed 3×3 cost matrix (not user-editable, same convention as this site's other fixed-content demos). Press Step or Run to watch one row at a time: dotted borders mark tight edges (reduced cost exactly 0, current potentials); a filled cell is currently matched; a solid dark cell is the edge just being evaluated; a solid accent cell is part of the augmenting path just found. Watch row W3 — it can't reach a free job through tight edges alone, needs two separate potential updates to open new tight edges, and its eventual augmenting path reassigns two already-matched pairs at once, not just one.
This is LP duality made concrete. Any set of potentials satisfying ui +
vj ≤ costij for every edge gives a cheap lower bound for free: for any
valid assignment, Σ costi,assign(i) ≥ Σ (ui + vassign(i)) = Σui +
Σvj (the second equality holds because a valid assignment touches every job exactly once, so
the vj terms are just a permutation of themselves). That sum of potentials never goes
down as the algorithm runs — the update step only ever raises it — so it's a lower bound that climbs toward the
true answer. The moment a perfect matching exists using only tight edges, every inequality above is
tight too, the lower bound equals the assignment's actual cost, and — since no assignment can beat its own lower
bound — that matching is provably cheapest. This is complementary slackness: an assignment is
optimal exactly when every edge it uses is tight for some feasible potentials.
The update step is what makes progress possible instead of the search dead-ending. When Kuhn's algorithm gets
stuck — every column reachable from the current tree's rows is already claimed, no free column sits behind a
tight edge — compute δ, the smallest slack (costij - ui - vj)
from any tree row to any column outside the tree. Raise every tree row's potential by δ and lower
every tree column's by δ. Tree-to-tree edges are unaffected (one side goes up, the other down, net
zero change to their sum). Tree-to-outside edges shrink by exactly δ — enough to make the
closest one newly tight, never enough to break feasibility elsewhere, since δ was chosen as the
minimum such slack. The equality subgraph strictly grows and the search never revisits a column it's
already ruled out, so this terminates in at most n tree-growth rounds per row.
The classic O(n³) row-by-row form: process one worker at a time, grow an alternating tree through the equality subgraph, raise/lower potentials whenever the tree gets stuck, augment once a free column is reached.
function hungarianAssignment(cost) {
// cost: n x n matrix, cost[i][j] = cost of assigning row i to column j. Minimizes total cost.
const n = cost.length;
const INF = Infinity;
const u = new Array(n + 1).fill(0); // row potentials (1-indexed, index 0 unused)
const v = new Array(n + 1).fill(0); // column potentials
const matchOfCol = new Array(n + 1).fill(0); // matchOfCol[j] = row currently assigned to column j
const way = new Array(n + 1).fill(0); // parent pointers through the alternating tree
for (let i = 1; i <= n; i++) {
matchOfCol[0] = i;
let j0 = 0;
const minSlack = new Array(n + 1).fill(INF);
const inTree = new Array(n + 1).fill(false);
do {
inTree[j0] = true;
const row = matchOfCol[j0];
let delta = INF, j1 = -1;
for (let j = 1; j <= n; j++) {
if (!inTree[j]) {
const slack = cost[row - 1][j - 1] - u[row] - v[j];
if (slack < minSlack[j]) { minSlack[j] = slack; way[j] = j0; }
if (minSlack[j] < delta) { delta = minSlack[j]; j1 = j; }
}
}
// delta is the smallest slack from any tree row to any column outside the tree — raising
// every tree row's potential and lowering every tree column's by delta makes that edge
// newly tight without ever violating u[i] + v[j] <= cost[i][j].
for (let j = 0; j <= n; j++) {
if (inTree[j]) { u[matchOfCol[j]] += delta; v[j] -= delta; }
else { minSlack[j] -= delta; }
}
j0 = j1;
} while (matchOfCol[j0] !== 0); // column j0 is unmatched — augmenting path found
// Walk back through the tree, reassigning each column to the row that reaches it.
do {
const j1 = way[j0];
matchOfCol[j0] = matchOfCol[j1];
j0 = j1;
} while (j0);
}
const assignment = new Array(n).fill(-1);
for (let j = 1; j <= n; j++) if (matchOfCol[j] > 0) assignment[matchOfCol[j] - 1] = j - 1;
let total = 0;
for (let i = 0; i < n; i++) total += cost[i][assignment[i]];
return { assignment, total };
}Checked against a brute-force assignment search (try every one of n! permutations, keep the
cheapest) across 3,000 randomly generated square cost matrices sized 2×2 through 5×5 — zero mismatches. Also
checked, on every trial's output: every matched edge's reduced cost is exactly 0 (complementary slackness) and
every potential pair satisfies ui + vj ≤ costij everywhere, not
just on matched edges (dual feasibility) — the optimality argument above only holds if both checks actually
pass on real output, not just "the total matches brute force."
Greedy, row by row, cheapest available job first, never revisited — lands on a valid but non-optimal assignment. On this page's own cost matrix, greedy gives W1–J1 (2), then W2's cheapest remaining option is J2 (6), leaving W3 stuck with J3 (9) — total 17. The true optimum, found by the potentials search above, is W1–J2, W2–J3, W3–J1 for a total of 15: strictly cheaper, but only reachable by giving up W1's "obviously fine" J1 pairing. Same shape of failure as greedy matching in the unweighted case, except here it isn't just short a pair — it's a valid complete assignment that silently costs more than necessary, with no signal anything went wrong.
Skipping the potential-update step doesn't just slow the search down — it can return a valid
assignment that's flatly wrong. On a different, smaller cost matrix chosen to expose this
([[2,5,5],[1,1,1],[4,6,5]]), running the same tree-growth search but never raising/lowering
potentials still terminates — every row eventually finds some column — and produces a complete assignment
totaling 10. The real optimum, from the algorithm above with potential updates included, is
8 (W1–J1, W2–J2, W3–J3). The broken version doesn't fail loudly: it returns a plausible-looking
answer that's simply not the cheapest one, because without updates the search can only ever compare rows against
the original costs, never against costs adjusted for what's already been committed elsewhere.
This construction needs a square cost matrix. If there are more workers than jobs (or vice versa), there's no perfect matching to find in the first place — the algorithm as coded here has no unmatched row or column left to terminate on cleanly. The standard fix is padding: add dummy rows or columns of cost 0 (if extra capacity should go unused for free) until the matrix is square, run unchanged, then discard any pairing involving a dummy in the result. That's a preprocessing step on the input, not a change to the algorithm above.
Time: O(n³) — n rows, each needing at most n
tree-growth rounds before an augmenting path is found (the equality subgraph strictly grows every round, so it
can't stall longer than that), each round scanning up to n columns to find the next candidate and
apply the potential update. Space: O(n²) for the cost matrix, O(n)
for the potentials and bookkeeping arrays.
See Choosing a Network Flow Algorithm for how this compares against the site's other ten Network Flow entries, including why it's a genuinely different kind of "best" from Minimum-Cost Maximum Flow rather than a more general version of it.