I have programmed the minimum Hungarian algorithm for a bipartite graph, with Dijkstra's algorithm to find the minimum cost of a maximum matching. However, I want to use such an algorithm to implement the maximum Hungarian algorithm and don't know if it's correct to just negate the edges, because I don't know if the algorithm will handle it.

My implementation is based on the explanation on the following site: https://www.ics.uci.edu/~eppstein/163/lecture6b.pdf

Given G=(AUB, E), the idea is to label the vertices via an artificial start vertex s which has edges with unsaturated nodes in A, and run Dijkstra's algorithm from s in order to label each vertex, then after labeling each, the edges will be reweighted by their original weight minus the labels of the edge's endpoints.

I have read a lot of articles, and the only I could see is that a minimum Hungarian algorithm can be handled well with maximum cost by negating each edge, however, I am afraid that due to the fact that Dijkstra's algorithm doesn't handle negative edges well, it won't work.

CodePudding user response：

First find the maximum weight in your graph. Then negate all of the weights and add the maximum weight to them. Adding the original maximum to all of the negated values makes them all positive.

You can also use INT_MAX (or whatever is equivalent to it in the programming language you're using) instead of the maximum weight. This skips the step of finding the maximum weight, but could make the first iteration of the Hungarian Algorithm take longer, or cause you to need an extra iteration of the algorithm to get the result. It probably doesn't make much of a difference either way and the performance difference will vary based on the particular weights in your graph.