非方阵的匈牙利算法

Question

我正在尝试实现匈牙利算法。除了矩阵不是方形的时候，一切都很好。我搜索过的所有方法都说我应该通过添加虚拟行/列并用矩阵中的最大数字填充虚拟行/列来使其成为正方形。我的问题是这不会影响最终结果吗？虚拟行/列不应该至少填充max+1 吗？

Answer 1

虚拟值应全部为零。关键是，无论您选择哪一个，您最终都会忽略这些选择，因为它们不在原始数据中。通过将它们设置为零（在开始时），您的算法将不必费力地找到您不会使用的值。