KuhnMunkresalgoritme

KuhnMunkresalgoritme, also known as the Hungarian algorithm, is an algorithm for solving the assignment problem. It was developed by Harold W. Kuhn in 1955 and refined by James Munkres in 1957. The algorithm finds a minimum-cost or maximum-weight perfect matching in a complete bipartite graph, equivalently an optimal assignment of n workers to n tasks given a cost matrix C = [cij]. It maintains dual variables (potentials) for rows and columns, commonly denoted ui and vj, such that ui + vj ≤ cij for a minimization version or ≥ for a maximization version; the algorithm utilizes an equality graph consisting of edges where ui + vj = cij. It repeatedly builds augmenting paths in this equality graph and augments the current matching. When no augmenting path exists, the labels are adjusted to create a new zero edge, preserving feasibility and enabling a new augmenting path. The procedure continues until a perfect matching is found, at which point the total cost is optimal.

Time complexity is O(n^3) for dense n×n matrices; variants exist for rectangular or sparse instances and for either minimizing or maximizing. Applications include operations research, scheduling, data association in computer vision, and other scenarios requiring optimal one-to-one assignment. The algorithm is named after Kuhn and Munkres and is sometimes referred to as the Hungarian algorithm.