Weighted bipartite matching

Question

I'm aware of there's a lot of similar topics. But most of them left me some doubts in my case. What I want to do is find perfect matching (or as close to perfect as possible in case there's no perfect matching of course) and then from all of those matchings where you are able to match k out of n vertexes (where k is highest possible), I want to choose the highest possible total weight. So simply put what I'm saying is following priority:

1. Match as many vertexes as possible
2. Because (non weighted) maximum matching in most cases is unambiguous, I want choose the one that have the biggest sum of weights on edges. If there are several of them with same weight it doesn't matter which would be chosen.

I've heard about Ford-Fulkerson algorithm. Is it working in the way I describe it or I need other algorithm?

Answer 1

If you're implementing this yourself, you probably want to use the Hungarian algorithm. Faster algorithms exist but aren't as easy to understand or implement.

Ford-Fulkerson is a maximum flow algorithm; you can use it easily to solve unweighted matching. Turning it into a weighted matcing algorithm requires an additional trick; with that trick, you wind up with the Hungarian algorithm.

You can also use a min-cost flow algorithm to do weighted bipartite matching, but it might not work quite as well. There's also the network simplex method, but it seems to be mostly of historical interest.