我编写了一个二部图的最小匈牙利算法，用Dijkstra算法找到最大匹配的最小代价。然而，我想用这样的算法来实现最大匈牙利算法，不知道它是否正确，只是否定边，因为我不知道算法是否会处理它。
我的实现是基于以下网站上的解释:https://www.ics.uci.edu/~eppstein/163/lecture6b.pdf
给定G=(AUB, E)，其思想是通过一个人工的起始顶点s标记顶点，该顶点在A中具有不饱和节点的边，并从s运行Dijkstra算法以标记每个顶点，然后在标记每个顶点后，边缘将被其原始权值减去边缘端点的标签重新加权。
我读了很多文章，我唯一能看到的是最小匈牙利算法可以通过否定每条边以最大的成本处理得很好，但是，我担心由于Dijkstra的算法不能很好地处理负边，它将不起作用。
首先找到图中的最大权重。然后消掉所有的权值，再加上最大的权值。将原始最大值与所有负值相加，使它们都为正。
您还可以使用INT_MAX(或在您正在使用的编程语言中与之等价的任何东西)代替最大权重。这跳过了查找最大权重的步骤，但是可能会使Hungarian Algorithm的第一次迭代花费更长的时间，或者导致需要对算法进行额外的迭代才能获得结果。这两种方法可能都不会产生太大的差异，性能差异将根据图中的特定权重而变化。