匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。
詹姆士·芒克勒斯在1957年回顾了该算法，并发现（强）多项式时间的。 此后该算法被称为Kuhn–Munkres算法或Munkres分配算法。原始算法的时间复杂度为，但Edmonds与卡普发现可以修改算法达到运行时间，富泽也独立发现了这一点。Ford和Fulkerson将该方法推广到了一般运输问题。2006年发现卡尔·雅可比在19世纪就解决了指派问题，该解法在他死后在1890年以拉丁文发表。

设定

给定一个 的非负矩阵，其中第 行第 列元素表示把第 个工人派到第个工作的成本。我们必须找到成本最低的工人工作分配。如果目标是找到最高成本的分配，该问题可以将每个成本都换为最高一个成本减去该成本以适应题目。
如果用二分图来阐述该问题可以更容易描述这个算法。对于一个有个工人节点（）与 个工作节点（）的完全二分图 ，每条边都有 的非负成本。我们要找到最低成本的完美匹配。
如果函数 满足对于每个 都有，则把该函数叫做势。势  的值为。可以看出，每个完美匹配的成本最低是每个势的值。匈牙利算法找出了完美匹配及与之成本/值相等的势，这证明了两者的最优性。实际上它找到了紧边集的完美匹配：紧边 是指对于势 满足 。我们将紧边子图表示为。 中的完美匹配的成本（如果存在）就等于的值。

用二分图描述此算法

在算法中我们维持 的势和方向（表示为 ），该方向有从到  的边构成匹配 的性质。初始时， 处处为0，
所有边都由 指向 （因此  为空）。每一步中，我们或者改变 使其值增加，
或者改变方向以得到更多的边。我们保持 的所有边都是紧边不发生改变。当  为完美匹配时结束。
在一般的步骤中，令  和  为  未覆盖的节点（则  包含  中入度为零的节点，而  中包含 中出度为零的节点）。
令  为从 只沿紧边的有向路径可到达 的节点。可由广度优先搜索求得。
若  非空，则将 中从 到  的有向路径反向。则相应匹配数增加1。
若  为空，则令。 为正，因为  与  之间没有紧边。
在  中的节点将增加 并在 中节点将减小，
得到的仍然是势。图  改变了，但它仍包含。我们把新的边从指向。
由  的定义， 可达的节点集 增大（注意到紧边的数量不一定增加）。
我们重复这些步骤直到为完美匹配，该情形下给出的是最小成本（即时间消耗）的匹配。此版本的运行时间为： 增广次，
在  不改变的一个阶段中，势最多改变 次（因为  每次都增加）。改变势所需的时间在。