Hungarian Algorithm (Kuhn-Munkres) — Interactive Visualization

Cost Matrix

Run

Slow Fast

The Idea

Reduced cost: c[i][j] - u[i] - v[j]
A tight edge has reduced cost 0.

Match on tight edges. When stuck, raise reached rows' u and lower reached columns' v by the slack δ — exposing a new tight edge without breaking reduced ≥ 0.

Optimality Certificate

When a perfect tight matching exists:
total cost = Σu + Σv
— the dual value proves the optimum.

Complexity

Time (solve)	O(n³)
Space	O(n²)
Query result	O(n)
Brute force	O(n·n!)

Click Sample or Random, then Run or Step.

n: 0

matched: 0

phase: -

δ updates: 0

Σu+Σv: 0

cost: -

tight edge (reduced = 0) matched pair reached row (alternating tree) δ slack / new tight edge

Hungarian Algorithm (Kuhn-Munkres) — Min-Cost Assignment

Operation Log