使用最小匈牙利法的最大加权匈牙利法
使用最小匈牙利法的最大加权匈牙利法
提问于 2022-06-02 22:17:03
我用Dijkstra的算法编写了二部图的最小匈牙利算法，以求最大匹配的最小代价。然而，我想使用这样的算法来实现最大匈牙利算法，并且不知道只否定边缘是否正确，因为我不知道算法是否会处理它。
我的实现是基于以下站点上的解释：https://www.ics.uci.edu/~eppstein/163/lecture6b.pdf
给定G=(AUB，E)，其思想是通过A中有不饱和节点边的人工起始点s对顶点进行标记，并运行Dijkstra算法对每个顶点进行标注，然后在每个顶点进行标记后，再用其初始权重减去边缘端点的标号对其进行重加权。
我读过很多文章，我唯一能看到的是，通过否定每一条边，可以以最大的代价很好地处理最小匈牙利算法，但是，由于Dijkstra的算法不能很好地处理负边，恐怕它不能工作。
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-06-02 23:09:35
首先，在你的图表中找到最大权重。然后否定所有权重，并将最大权重添加到其中。将原来的最大值添加到所有被否定的值中，使它们都为正。
您还可以使用INT_MAX (或者在您正在使用的编程语言中与其等效的任何东西)，而不是使用最大权重。这跳过了寻找最大权重的步骤，但可能会使匈牙利算法的第一次迭代时间更长，或者导致您需要对算法进行额外的迭代才能得到结果。无论是哪种方式，它可能都不会有太大的差别，而且性能差异将根据图表中的特定权重而有所不同。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/72482869
复制相关文章
相似问题
腾讯云开发者
