01 / The idea
The cheapest pair can leave an expensive pair behind.
Atlas can reach Dock in 2 minutes or Garden in 3. Beacon can also reach Dock in 3, but Garden costs 40. If a greedy policy spends Dock on Atlas, Beacon inherits the expensive column.
Hungarian assignment minimizes the sum of one selected cell from every row and every column. It solves a one-to-one allocation, not the order in which a robot should visit multiple pickups.
The lesson’s matrix makes the contrast visible: greedy pays 44 minutes, while the global assignment sends Atlas to Garden and Beacon to Dock for a total of 8.
Match every robot without stranding the last pickup.
| Robot ↓ Pickup → | Dock | Garden | Hall | Intake |
|---|---|---|---|---|
| Atlas | 2 | 3 | 40 | 40 |
| Beacon | 3 | 40 | 40 | 40 |
| Comet | 40 | 40 | 1 | 4 |
| Dune | 40 | 40 | 4 | 1 |
Every cell is a possible one-to-one choice.
chosen pair still available
Read the whole cost matrix.
Each row is a robot and each column is a pickup. The number is a travel cost, but every robot and every pickup may be used exactly once.
Reduced motion: choose a scene to see its completed state.
Read this scene
Each row is a robot and each column is a pickup. The number is a travel cost, but every robot and every pickup may be used exactly once.
Four agents, four pickups, and sixteen possible costs are visible. No choice is final yet.
Watch and Step through replay the same cost matrix. Try it runs the real assignment function with a second matrix.
Once the robots start joining, the matrix shows reduced costs, and the zeros are the pairs the algorithm may use. Atlas’s row drops by 2, so Dock becomes a zero and Atlas takes it. When Beacon arrives wanting Dock too, the potentials shift until Atlas → Garden is also a zero, and the exchange moves Atlas there. Comet and Dune take their own one-minute zeros.
02 / Name the rule
Make good choices visible as zeros.
Subtracting a constant from a whole row, or a whole column, changes every complete assignment’s total by the same amount, so the cheapest assignment stays the cheapest. The textbook version starts by subtracting each row’s and column’s smallest value to create zero-cost opportunities.
The implementation stores row and column potentials. A reduced cost is cost − rowPotential − columnPotential. Instead of reducing everything up front, it starts every potential at zero and adds one
robot at a time: the augmenting search walks through zero-cost opportunities, and when it
cannot finish, it shifts the potentials by the smallest uncovered reduced cost.
Expose equalities
Subtracting a constant from a whole row or column does not change which complete assignments are cheapest.
Flip a matching path
Add a new agent while exchanging an earlier pair if the equality graph offers a better complete shape.
Cover every row and column
When n zero-cost pairs cover n rows and n columns, their original costs form a minimum assignment.
The key invariant is dual feasibility: all reduced costs stay non-negative. A zero is a candidate pair, and a complete set of independent zeros is a certificate that the original total is optimal.
Why not pick any zero?A zero can still block another row
After reductions there may be several zeros in the same row or column. Selecting one without considering the rest can strand a row. Hungarian grows an augmenting path so an earlier selection can move while the matching remains one-to-one.
03 / Read the shape
The matrix stays; the potentials move.
Basic form is solveAssignment: the potential-based loop that
adds one robot per row and augments the matching. In the wild adds the
types, validation, the cheapest-pair greedy baseline, and the snapshot copies the film
reads. At the call site compares the greedy baseline with the global assignment and
prints the savings.
solveAssignment: add one robot per row, use row and column potentials to find the cheapest augmenting path, and grow a one-to-one matching.
/**
* Kuhn–Munkres / Hungarian algorithm for a square minimum-cost assignment.
* The potentials are the row and column reductions; a zero reduced cost is a
* currently viable edge in the equality graph.
*/
export function solveAssignment(problem: AssignmentProblem): AssignmentResult {
const n = validate(problem);
const u = Array<number>(n + 1).fill(0);
const v = Array<number>(n + 1).fill(0);
const matchByPickup = Array<number>(n + 1).fill(0);
const way = Array<number>(n + 1).fill(0);
const snapshots: AssignmentSnapshot[] = [];
for (let row = 1; row <= n; row += 1) {
matchByPickup[0] = row;
let pickup = 0;
const minv = Array<number>(n + 1).fill(Number.POSITIVE_INFINITY);
const used = Array<boolean>(n + 1).fill(false);
way.fill(0);
let delta: number;
do {
used[pickup] = true;
const currentRow = matchByPickup[pickup];
delta = Number.POSITIVE_INFINITY;
let nextPickup = 0;
for (let candidate = 1; candidate <= n; candidate += 1) {
if (used[candidate]) continue;
const reduced = problem.costs[currentRow - 1][candidate - 1] - u[currentRow] - v[candidate];
if (reduced < minv[candidate]) {
minv[candidate] = reduced;
way[candidate] = pickup;
}
if (minv[candidate] < delta || (minv[candidate] === delta && candidate < nextPickup)) {
delta = minv[candidate];
nextPickup = candidate;
}
}
for (let candidate = 0; candidate <= n; candidate += 1) {
if (used[candidate]) {
u[matchByPickup[candidate]] += delta;
v[candidate] -= delta;
} else {
minv[candidate] -= delta;
}
}
pickup = nextPickup;
} while (matchByPickup[pickup] !== 0);
do {
const previousPickup = way[pickup];
matchByPickup[pickup] = matchByPickup[previousPickup];
pickup = previousPickup;
} while (pickup !== 0);
const columns = Array.from({ length: n }, (_, index) => {
const matchedRow = matchByPickup[index + 1];
return matchedRow === 0 ? -1 : matchedRow - 1;
});
snapshots.push(snapshot(problem, row, problem.agents[row - 1], delta, columns, u, v));
}
const columns = Array.from({ length: n }, (_, index) => matchByPickup[index + 1] - 1);
const summary = summaryFromColumns(problem, columns);
return {
...summary,
snapshots,
rowPotentials: u.slice(1),
columnPotentials: v.slice(1),
reducedCosts: problem.costs.map((costs, rowIndex) =>
costs.map((cost, columnIndex) => cost - u[rowIndex + 1] - v[columnIndex + 1])
)
};
}// solveAssignment implements the Kuhn–Munkres / Hungarian algorithm.
func solveAssignment(problem AssignmentProblem) (AssignmentResult, error) {
n, err := validate(problem)
if err != nil {
return AssignmentResult{}, err
}
u := make([]int, n+1)
v := make([]int, n+1)
matchByPickup := make([]int, n+1)
snapshots := make([]AssignmentSnapshot, 0, n)
for row := 1; row <= n; row++ {
matchByPickup[0] = row
pickup := 0
minv := make([]int, n+1)
used := make([]bool, n+1)
way := make([]int, n+1)
for i := range minv {
minv[i] = infinity
}
delta := 0
for {
used[pickup] = true
currentRow := matchByPickup[pickup]
delta = infinity
nextPickup := 0
for candidate := 1; candidate <= n; candidate++ {
if used[candidate] {
continue
}
reduced := problem.Costs[currentRow-1][candidate-1] - u[currentRow] - v[candidate]
if reduced < minv[candidate] {
minv[candidate] = reduced
way[candidate] = pickup
}
if minv[candidate] < delta || (minv[candidate] == delta && candidate < nextPickup) {
delta = minv[candidate]
nextPickup = candidate
}
}
for candidate := 0; candidate <= n; candidate++ {
if used[candidate] {
u[matchByPickup[candidate]] += delta
v[candidate] -= delta
} else {
minv[candidate] -= delta
}
}
pickup = nextPickup
if matchByPickup[pickup] == 0 {
break
}
}
for pickup != 0 {
previousPickup := way[pickup]
matchByPickup[pickup] = matchByPickup[previousPickup]
pickup = previousPickup
}
columns := make([]int, n)
for i := range columns {
columns[i] = matchByPickup[i+1] - 1
}
snapshots = append(snapshots, makeSnapshot(problem, row, problem.Agents[row-1], delta, columns, u, v))
}
columns := make([]int, n)
for i := range columns {
columns[i] = matchByPickup[i+1] - 1
}
summary := summaryFromColumns(problem, columns)
return AssignmentResult{
AssignmentSummary: summary,
Snapshots: snapshots,
RowPotentials: cloneInts(u[1:]),
ColumnPotentials: cloneInts(v[1:]),
ReducedCosts: cloneMatrix(snapshots[len(snapshots)-1].ReducedCosts),
}, nil
}Reading the TypeScriptPotentials and augmenting paths
u and v are row and column potentials. matchByPickup records which row currently owns each column, while way recovers the alternating
path when a free column is reached.
Reading the GoThe same indexed matrix
Go uses the same one-indexed Hungarian loop with integer costs and returns the same per-row snapshots (the film on this page replays the TypeScript ones). Both languages list the final pairs in input order, so they print the same answer for any labels.
What is refusedA clear objective
Both versions require a non-empty square matrix, unique lowercase labels, and whole costs from 0 through 10,000. Rectangular or forbidden assignments need a different contract, such as padding or an explicit missing-pair cost.
04 / Try a decision
Who should get the flexible pickup?
Look at the first bargain and the rows and columns it removes. Choose the reason greedy pairing can strand the remaining robot.
05 / Follow the cost
Pay cubic time for a global answer.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Validate the matrix | O(n²) | O(1) | Read every cell once and require one row per agent and one column per pickup. |
| Find one assignment | O(n³) | O(n³) as shown | Each of the n rows runs up to n search steps, and each step scans n columns. The shown code also stores one n × n reduced-cost snapshot per row for the film: O(n³) extra space. Without the snapshots the solver needs only O(n) extra. |
| Store the costs | — | O(n²) | The algorithm needs the matrix and a reduced-cost view; it does not need a route graph. |
| Compare greedy | O(n² log n) | O(n²) | Sorting all cells makes a useful baseline, but it provides no global optimality guarantee. |
With n agents and n pickups, the Hungarian algorithm takes O(n³) time. Reading the matrix is O(n²); the cubic work comes from repeated augmenting searches and potential updates. Beyond the n × n matrix, the solver itself needs only O(n) extra space, but the version shown keeps a reduced-cost snapshot after each row for the film, which makes it O(n³). Drop the snapshots in production.
The algorithm is a good fit for small or medium allocation batches. For a huge sparse or streaming problem, the matrix itself may be the dominant cost, and a specialized min-cost-flow or sparse assignment formulation may fit better.
06 / Give it a real job
Dispatch one batch at a time.
A warehouse dispatcher collects the robots that are free and the pickups that are waiting,
every few seconds, and builds the matrix from its travel-time estimates. It calls solveAssignment on that batch, sends each robot its pickup, and starts the next batch
with whatever is left. The batch is small, so the O(n³) solve takes far less time than the robots
take to move.
The solver owns one decision: who takes which pickup in this batch, at the lowest total. It doesn’t own the travel times, which come from the routing service, and it doesn’t plan a robot’s path or a string of stops. The shown code also refuses a batch that isn’t square. When five pickups wait for four robots, the dispatcher adds a fifth, imaginary robot whose row costs the same for every pickup. That adds the same amount to every complete assignment, so the real robots still get the cheapest pickups, and the one the imaginary robot takes waits for the next batch.
This runs on the dispatch server that knows every robot and every open pickup; nothing in a component computes it.
07 / Make the call
Define “best” before matching.
Use Hungarian assignment when every agent gets at most one task, every task has one owner, and the objective is the sum of independent pair costs. It is useful for dispatch batches, workers to shifts, or machines to jobs.
Use Dijkstra when the problem is a path through a graph, not a pair in a matrix. Use Gale–Shapley when stability under preferences matters more than minimizing a numeric cost.
The cheapest-pair greedy is quicker to write and to run, and it is sometimes the fallback when a batch is too big to solve before the robots need orders. Know what it can cost: on this matrix it pays 44 minutes where 8 were possible.
08 / Take the idea with you
Explain the dispatch without saying “Hungarian.”
“Write every robot’s cost to every pickup in a table. Take the same amount off a whole row or a whole column until good pairs show up as zeros, since that never changes which complete plan is cheapest. Add robots one at a time. When a new robot wants a pickup someone holds, keep shifting rows and columns the same way until the holder has another zero to move to, then move it. When every robot sits on its own zero, no plan can cost less.”
Before moving on, think of a place where one-to-one choices are made in order, such as reviewers picking papers or drivers taking the next job. Ask what the first cheap pick costs the last person to choose.
Connections to follow nextRelated lessons
- Graph overview gives the bipartite picture: robots on one side, pickups on the other, and a cost on every edge.
- Max flow and min cut finds how many pairs can be made at all; give each edge a cost as well and the assignment here is the cheapest way to make n of them.
- Gale–Shapley matches from ranked preferences and promises stability, not the lowest total.