{"id":6728,"library":"munkres","title":"Munkres (Hungarian) Algorithm","description":"The `munkres` library (version 1.1.4) provides a Python implementation of the Munkres (also known as the Hungarian) algorithm for solving the assignment problem, which aims to find a minimum-cost bipartite matching. It typically runs in O(n^3) time. While its original GitHub repository (linked on PyPI) is marked as unmaintained, the PyPI package remains available and provides a robust solution for assignment problems.","status":"maintenance","version":"1.1.4","language":"python","source_language":"en","source_url":"https://github.com/bmc/munkres","tags":["algorithm","assignment-problem","optimization","mathematics","bipartite-matching"],"install":[{"cmd":"pip install munkres","lang":"bash","label":"Install latest version"}],"dependencies":[],"imports":[{"note":"The primary class for running the algorithm.","symbol":"Munkres","correct":"from munkres import Munkres"},{"note":"Constant to mark impossible assignments in the cost matrix.","symbol":"DISALLOWED","correct":"from munkres import Munkres, DISALLOWED"}],"quickstart":{"code":"from munkres import Munkres, DISALLOWED\n\ndef create_cost_matrix():\n    # Example cost matrix: 3 workers, 3 tasks\n    # cost[i][j] is cost of worker i doing task j\n    return [\n        [5, 9, 1],\n        [10, 3, DISALLOWED],\n        [8, 7, 4]\n    ]\n\nm = Munkres()\nmatrix = create_cost_matrix()\n\n# The algorithm operates on a copy of the matrix,\n# so the original 'matrix' is not modified.\nindexes = m.compute(matrix)\n\ntotal_cost = 0\nprint('Assignments:')\nfor row, column in indexes:\n    value = matrix[row][column]\n    total_cost += value\n    print(f'  Worker {row} assigned to task {column} with cost {value}')\n\nprint(f'Total cost: {total_cost}')","lang":"python","description":"This quickstart demonstrates how to create a cost matrix, initialize the Munkres solver, and compute the optimal (minimum cost) assignments. It also shows how to use the `DISALLOWED` constant for impossible assignments. The `compute` method returns a list of (row, column) tuples representing the optimal assignments."},"warnings":[{"fix":"Upgrade to Python 3 or use `munkres` version < 1.1.0 if Python 2 is strictly required.","message":"As of version 1.1.0, the `munkres` library dropped support for Python 2. Users on Python 2 must use an older version (pre-1.1.0).","severity":"breaking","affected_versions":">=1.1.0"},{"fix":"Transform your profit matrix `P` into a cost matrix `C` by `C[i][j] = MAX_PROFIT - P[i][j]`, where `MAX_PROFIT` is greater than or equal to any profit in the matrix.","message":"The Munkres algorithm natively solves minimization problems. To solve maximization problems (e.g., maximizing profit), the cost matrix must be transformed. A common approach is to subtract all matrix elements from a sufficiently large constant (e.g., the maximum value in the matrix).","severity":"gotcha","affected_versions":"All"},{"fix":"Be aware that the input matrix is copied and potentially padded. If you need to observe the padded matrix for debugging or further processing, manually pad it before passing it to `Munkres.compute()`.","message":"The `munkres` module automatically pads rectangular cost matrices with zeros to make them square, as the algorithm requires a square matrix. However, this operation works on a *copy* of the input matrix, so the caller's original matrix is not modified.","severity":"gotcha","affected_versions":"All"},{"fix":"Ensure that your `DISALLOWED` constraints still allow for at least one valid assignment path for every row and column. If intentional non-assignments are needed, `munkres` does not directly support 'no match' if it leads to an unsolvable matrix. Consider augmenting your matrix with dummy rows/columns with zero costs to represent unassigned items if that aligns with your problem.","message":"Using the `DISALLOWED` constant correctly marks an assignment as impossible. However, if using `DISALLOWED` results in a scenario where a row or column has no possible valid assignments, the `compute` method will raise an `UnsolvableMatrix` exception, indicating that no complete assignment can be found under the given constraints.","severity":"gotcha","affected_versions":"All"},{"fix":"If encountering issues, avoid `print_matrix()` and implement a custom matrix printing function, or ensure only positive values are passed to it.","message":"The utility function `munkres.print_matrix()` might raise a `ValueError` (e.g., `math.log10(0)`) if the matrix contains zero values, especially in older versions or specific Python environments. This function is for display and does not affect the core algorithm.","severity":"gotcha","affected_versions":"<=1.1.4 (potentially fixed in future, but reported in past)"}],"env_vars":null,"search_vec":"'1.1.4':8 '3':43 'aim':28 'algorithm':3,21,70 'also':16 'assign':25,68,72 'assignment-problem':71 'avail':61 'bipartit':35,77 'bipartite-match':76 'cost':34 'find':30 'github':48 'hungarian':2,20 'implement':12 'known':17 'librari':6 'link':50 'mark':54 'match':36,78 'mathemat':75 'minimum':33 'minimum-cost':32 'munkr':1,5,15 'n':42 'o':41 'optim':74 'origin':47 'packag':59 'problem':26,69,73 'provid':9,63 'pypi':52,58 'python':11 'remain':60 'repositori':49 'robust':65 'run':39 'solut':66 'solv':23 'time':44 'typic':38 'unmaintain':56 'version':7","created_at":"2026-04-15T18:40:24.854255+00:00","updated_at":"2026-04-16T16:43:24.940990+00:00","problems":[{"fix":"Install the library using pip: `pip install munkres`","cause":"The `munkres` library has not been installed in your Python environment or the environment where you are running your script.","error":"ModuleNotFoundError: No module named 'munkres'"},{"fix":"Avoid using `munkres.print_matrix` with matrices containing zero values. Instead, iterate through the matrix and print it manually, or implement a custom printing function that handles zeros appropriately:\n```python\ndef custom_print_matrix(matrix):\n    for row in matrix:\n        print('  '.join([str(x) for x in row]))\n\n# Example usage:\n# from munkres import Munkres\n# m = Munkres()\n# matrix = [,,]\n# indexes = m.compute(matrix)\n# custom_print_matrix(matrix)\n```","cause":"The `print_matrix` utility function in the `munkres` library attempts to use `math.log10` to format column widths, which raises a `ValueError` if any matrix element is zero because `log10(0)` is undefined.","error":"ValueError: math domain error (from print_matrix function when matrix contains zeros)"},{"fix":"Ensure your problem fits the definition of a bipartite matching problem. If you need to solve a general matching problem (non-bipartite), consider using an algorithm like the Blossom algorithm, which is implemented in libraries such as SciPy's `scipy.optimize.linear_sum_assignment` for linear sum assignment (which `munkres` also does) or dedicated graph libraries for general matching.","cause":"The Munkres (Hungarian) algorithm solves the *assignment problem* on *bipartite graphs* (e.g., matching workers to jobs with minimum cost). If you are trying to solve a more general matching problem (e.g., matching users to other users within a single set), the `munkres` library will not provide the correct or optimal solution because it's designed for a specific type of problem.","error":"Incorrect assignment results or non-optimal solutions (conceptual error)"}],"ecosystem":"pypi","meta_description":null,"install_score":null,"quickstart_score":null,"quickstart_tag":null,"pypi_latest":"1.1.4","cli_name":"","cli_version":null,"type":"library","homepage":"https://software.clapper.org/munkres/","github":null,"docs":null,"changelog":null,"pypi":"https://pypi.org/project/munkres/","npm":null,"openapi_spec":null,"status_page":null,"smithery":null,"categories":["data","ai-ml"],"base_url":null,"auth_type":null,"provenance":{"verified_status":"passing","verified_at":"2026-06-28","last_verified":"2026-06-28","next_check":"2026-07-28","install_tag":null}}