最大加权匈牙利法 使用最小匈牙利法
Maximum weighted Hungarian method Using minimum Hungarian method
我编写了二分图的最小匈牙利算法，使用 Dijkstra 算法找到最大匹配的最小成本。但是，我想用这样的算法来实现最大匈牙利算法，不知道只对边求反是否正确，因为我不知道算法是否会处理。
我的实现基于以下站点上的解释：https://www.ics.uci.edu/~eppstein/163/lecture6b.pdf
给定 G=(AUB, E)，想法是通过人工起始顶点 s 标记顶点，该起始顶点 s 具有 A 中不饱和节点的边，并且 运行 来自 s 的 Dijkstra 算法以便标记每个顶点，然后在标记每个顶点之后，边缘将通过其原始权重减去边缘端点的标签来重新加权。
我看了很多文章，我唯一能看到的是最小匈牙利算法可以通过对每条边取反来以最大成本很好地处理，但是，恐怕由于 Dijkstra 算法不能很好地处理负边缘，它不会起作用。
首先找出图表中的最大权重。然后将所有权重取反并向它们添加最大权重。将原始最大值添加到所有否定值使它们都是正值。
您也可以使用 INT_MAX（或您正在使用的编程语言中的任何等效项）代替最大权重。这会跳过寻找最大权重的步骤，但可能会使匈牙利算法的第一次迭代花费更长的时间，或者导致您需要额外的算法迭代才能获得结果。这两种方式可能都没有太大区别，性能差异会根据图表中的特定权重而有所不同。
我编写了二分图的最小匈牙利算法，使用 Dijkstra 算法找到最大匹配的最小成本。但是，我想用这样的算法来实现最大匈牙利算法，不知道只对边求反是否正确，因为我不知道算法是否会处理。
我的实现基于以下站点上的解释：https://www.ics.uci.edu/~eppstein/163/lecture6b.pdf
给定 G=(AUB, E)，想法是通过人工起始顶点 s 标记顶点，该起始顶点 s 具有 A 中不饱和节点的边，并且 运行 来自 s 的 Dijkstra 算法以便标记每个顶点，然后在标记每个顶点之后，边缘将通过其原始权重减去边缘端点的标签来重新加权。
我看了很多文章，我唯一能看到的是最小匈牙利算法可以通过对每条边取反来以最大成本很好地处理，但是，恐怕由于 Dijkstra 算法不能很好地处理负边缘，它不会起作用。
首先找出图表中的最大权重。然后将所有权重取反并向它们添加最大权重。将原始最大值添加到所有否定值使它们都是正值。
您也可以使用 INT_MAX（或您正在使用的编程语言中的任何等效项）代替最大权重。这会跳过寻找最大权重的步骤，但可能会使匈牙利算法的第一次迭代花费更长的时间，或者导致您需要额外的算法迭代才能获得结果。这两种方式可能都没有太大区别，性能差异会根据图表中的特定权重而有所不同。