$ Paldita Munkres
The Munkres (Hungarian) algorithm for the assignment problem
munkres.py
$ pip install munkres==2.0.0
$ python
>>> 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)]
2
Stars
0
Forks
4
Open Issues
Apache 2.0
License
Python
Language
$ Features
--pure-python
Zero dependencies. Runs anywhere Python runs. No C extensions, no external libraries.
--fully-typed
Complete type hints for static analysis and better IDE support. Catch bugs before runtime.
--thread-safe
Use multiple instances of Munkres in parallel without data races. Perfect for concurrent applications.
--disallowed-pairing
Explicitly forbid worker-job pairs with `DISALLOWED` or `float('inf')`. No more impossible assignments.
--maximize-profit
Turn profit maximization into a cost minimization problem with `make_cost_matrix`.
--rich-results
The `solve()` function returns objects with pairs, totals, unmatched items, and optimality certificates.
$ Quick Start
basic_usage.py
from munkres import Munkres
cost = [[4, 1, 3],
[2, 0, 5],
[3, 2, 2]]
munkres = Munkres()
pairs = munkres.compute(cost)
print(pairs) # [(0, 1), (1, 0), (2, 2)]
print(sum(cost[r][c] for r, c in pairs)) # 5
forbidding_a_pairing.py
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)]
maximizing_profit.py
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