munkres

The Munkres (Hungarian) algorithm for the assignment problem: given a cost for every (worker, job) pair, find the one-to-one assignment with the lowest total cost. Pure Python, no dependencies, fully typed, thread-safe.

            Job A  Job B  Job C
Worker 0      4      1      3
Worker 1      2      0      5        ->   0->B (1)   1->A (2)   2->C (2)   total 5
Worker 2      3      2      2

Install

pip install munkres==3.0.0
pip install git+https://github.com/iameishit/Paldita-munkres

Needs Python 3.10+. numpy and pandas are optional: if you have them, arrays and DataFrames are accepted as input.

Quick start

from munkres import Munkres

cost = [[4, 1, 3],
        [2, 0, 5],
        [3, 2, 2]]

pairs = Munkres().compute(cost)
print(pairs)                                   # [(0, 1), (1, 0), (2, 2)]
print(sum(cost[r][c] for r, c in pairs))       # 5

compute returns (row, column) pairs sorted by row. Rectangular matrices work too: min(rows, columns) pairs are returned.

Forbidding a pairing

from munkres import DISALLOWED, Munkres

cost = [[4, DISALLOWED, 3],
        [2, 0, DISALLOWED],
        [3, 2, 2]]
print(Munkres().compute(cost))                 # [(0, 2), (1, 1), (2, 0)]

float("inf") means the same as DISALLOWED.

Maximising profit instead of minimising cost

from munkres import Munkres, make_cost_matrix

profit = [[5, 9, 1], [10, 3, 2], [8, 7, 4]]
pairs = Munkres().compute(make_cost_matrix(profit))
print(sum(profit[r][c] for r, c in pairs))     # 23

When there is no valid assignment

Impossible constraints raise immediately (they used to hang forever in 1.x), and the exception tells you why:

from munkres import DISALLOWED as D, Munkres, UnsolvableMatrix

try:
    Munkres().compute([[1, D, D], [1, D, D], [1, 2, 3]])
except UnsolvableMatrix as error:
    print(error)       # No complete assignment exists: rows [0, 1] can only be matched to columns [0] ...
    print(error.rows, error.cols)              # (0, 1) (0,)

numpy and pandas

import numpy as np
from munkres import Munkres

print(Munkres().compute(np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])))

Inputs are never modified. Fraction and Decimal costs work as well.

More than compute()

A richer result: solve

from munkres import solve

result = solve([[4, 1, 3], [2, 0, 5]])         # 2 workers, 3 jobs
print(result.pairs)                            # ((0, 1), (1, 0))
print(result.total)                            # 3
print(result.unmatched_cols)                   # (2,)

maximize=True maximises (exactly, even for Decimal/Fraction). Gating (max_cost=, or min_profit= when maximising) refuses bad pairs and leaves rows unmatched instead, which is what object tracking needs:

from munkres import solve

cost = [[1, 9, 9], [9, 2, 9], [9, 9, 8]]
print(solve(cost, max_cost=3).pairs)           # ((0, 0), (1, 1))
profit = [[5, 9, 1], [10, 3, 2], [8, 7, 4]]
print(solve(profit, maximize=True).total)      # 23

With a pandas DataFrame you get your labels back:

import pandas as pd
from munkres import solve

frame = pd.DataFrame([[4, 1], [2, 0]], index=["w1", "w2"], columns=["jobA", "jobB"])
print(solve(frame).labelled())                 # [('w1', 'jobB'), ('w2', 'jobA')]

Why is there no answer? diagnose

from munkres import DISALLOWED as D, diagnose

problem = diagnose([[1, D, D], [1, D, D], [1, 2, 3]])
print(problem.rows, problem.cols)              # (0, 1) (0,)

Watch it think: trace

from munkres import solve

trace = solve([[4, 1, 3], [2, 0, 5], [3, 2, 2]], trace=True).trace
print(trace.to_text().splitlines()[0])         # Hungarian algorithm on a 3x3 matrix (10 steps)

trace.to_html() gives a static page you can open or share.

Drop-in for SciPy, and a matrix builder

from munkres import build_cost_matrix, linear_sum_assignment, solve

rows, cols = linear_sum_assignment([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
print(rows, cols)                              # [0, 1, 2] [1, 0, 2]
workers, jobs = [(0, 0), (5, 5)], [(1, 1), (6, 4)]
cost = build_cost_matrix(workers, jobs, lambda w, j: abs(w[0] - j[0]) + abs(w[1] - j[1]))
print(solve(cost).pairs)                       # ((0, 0), (1, 1))

Analysing a problem

from munkres import bottleneck, counterfactual, k_best, shadow_prices, tolerance

m = [[4, 1, 3], [2, 0, 5], [3, 2, 2]]
print(shadow_prices(m).total)                  # 5
print(counterfactual(m, 0, 0))                 # 1
print(tolerance(m, 0, 1))                      # 1
print([a.total for a in k_best(m, 3)])         # [5, 6, 6]
print(bottleneck([[1, 5], [5, 9]]).pairs)      # ((0, 1), (1, 0))

• shadow_prices: the LP duals, a certificate anyone can re-check that the answer is optimal.
• counterfactual(m, i, j): what forcing a pair would cost. tolerance(m, i, j): how much a chosen pair's cost may rise before the answer changes.
• k_best(m, k): the k best assignments (Murty's algorithm).
• bottleneck(m): make the worst single pair as good as possible.

Related problems

from munkres import soft_assignment, stable_matching, transport

men = {"A": ["x", "y", "z"], "B": ["y", "x", "z"], "C": ["x", "y", "z"]}
women = {"x": ["B", "A", "C"], "y": ["C", "A", "B"], "z": ["A", "B", "C"]}
print(stable_matching(men, women))             # {'A': 'z', 'B': 'x', 'C': 'y'}
plan = transport([3, 2], [2, 3], [[1, 5], [4, 2]])
print(plan.flows)                              # {(0, 0): 2, (0, 1): 1, (1, 1): 2}
print(plan.total_cost)                         # 11
print(round(soft_assignment([[0.0, 1.0, 1.0], [1.0, 0.0, 1.0], [1.0, 1.0, 0.0]], 0.05)[0][0], 3))  # 1.0

• stable_matching: preferences instead of costs (Gale-Shapley, proposer-optimal).
• transport: ship quantities from suppliers to consumers at least cost.
• sinkhorn / soft_assignment: entropic optimal transport, a soft, differentiable matching.

What is new in v3 (development)

An optional C kernel makes dense solves as fast as SciPy's from about 64x64 up, and much faster when you solve many small problems at once (solve_batch); without a compiler everything still works in pure Python. On top of the solver there is a layer you can trust and inspect:

import munkres as mk

cost = [[4, 1, 3], [2, 0, 5], [3, 2, 2]]

res = mk.solve_planned(cost, verify=True)            # plan, solve, then an independent exact proof
print(res.total, res.certificate.verify(cost).ok)    # 5 True

top = mk.topology(cost)                              # which cells are forced / optional across all optima
print(top.unique, top.n_optimal)                     # True 1
print(mk.canonical_optimum(cost))                    # ((0, 1), (1, 0), (2, 2))
print(mk.explain_edge(cost, 0, 1)[:40])              # cell (0, 1) is forced (in every optim...

state = mk.AssignmentState(cost)                     # costs change? repair instead of re-solving
state.update_cost(0, 0, 9)
print(state.objective, bool(state.verify()))         # 5 True

print(mk.solve_spec({"cost": [[1, 2], [2, None]], "verify": True})["total"])   # 4
try:
    mk.solve_limited(cost, mk.SolverLimits(max_cells=4))   # refuses before allocating anything
except mk.ProblemTooLargeError as err:
    print(err.code)                                  # CELLS_LIMIT

Everything above is exact (integers, fractions, or floats treated as the exact rationals they are) and is checked against brute force in the test-suite. The full list is in docs/api.md; the research ideas behind it, with an honest status for each of the 300, are in; the design and its limits are in docs/V3_ARCHITECTURE.md. munkres doctor shows whether the native kernel is active.

Honest limits: tiny matrices (about 10x10 and below) are slower than SciPy because of Python call overhead; heavily forbidden large matrices (90% forbidden at 256x256) are slower too; the exact tools (topology, enumerate_optima, AssignmentState, ...) are meant for small and medium problems; quantum/Ising helpers are classical simulations, not quantum hardware.

Production safety

The native accelerator is optional and can never break your program: if it is missing, rejected by its load-time self-test, or raises at runtime, the call finishes on the exact pure-Python solver and a circuit breaker switches the kernel off after repeated failures. Check munkres.native_status() in your health checks; see docs/production.md.

SciPy-compatible functions

linear_sum_assignment(cost, maximize=False) and min_weight_full_bipartite_matching(biadjacency, maximize=False) have the same calls as their SciPy counterparts (when several optimal answers exist the one returned may differ; the total is always the same).

Command line

munkres costs.csv --maximize --json
printf '4,1,3\n2,0,5\n3,2,2\n' | munkres - --trace

Matrix files are comma- or space-separated; an empty cell, D, x or inf forbids a pairing. python -m munkres with no arguments runs a built-in self-check.

Input rules

input	result
ragged rows	ValueError
NaN, -inf	ValueError
a non-number cell	TypeError
empty matrix (no rows or no columns)	[]
DISALLOWED, +inf	pairing forbidden
impossible constraints	UnsolvableMatrix (a ValueError) with a Hall's-theorem witness

Performance

On NumPy input, munkres 3.0 runs at about the same speed as SciPy's linear_sum_assignment in this range (0.75x to 1.04x across 50x50 to 1000x1000 random matrices, same optimum). It is competitive, not uniformly faster. The full table and method are in docs/BENCHMARKS.md.

Migrating from 1.x

2.0 keeps the Munkres().compute(), make_cost_matrix, print_matrix, DISALLOWED and UnsolvableMatrix API, and Munkres().compute() is not deprecated. What changed:

• ragged matrices now raise ValueError (they used to be silently mis-solved);
• NaN / -inf raise ValueError (they used to hang), +inf = DISALLOWED;
• impossible matrices raise UnsolvableMatrix (they used to hang);
• Python 3.10+ only; setup.py is gone (pyproject.toml).

See CHANGELOG.md for the full list.

What's new in 3.0.0

The first stable 3.x release: an optional native kernel with automatic fallback, exact certificates and an independent verifier, a planner that explains its choices, dynamic updates, and structure tools. Full details: V3_RELEASE.txt and CHANGELOG.md.

Development

See CONTRIBUTING.md. In short: pip install -e . and tools/audit.sh.

Credits and license

Created by Brian M. Clapper (2008-2020); maintained and extended since 2026 by Eishit Nigam. Licensed under the Apache License 2.0; see NOTICE.