{"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":"en","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,"last_verified":"2026-04-15T00:00:00.000Z","next_check":"2026-07-14T00:00:00.000Z","problems":[]}