I am looking for a simple way of calculating minimum-weight perfect matchings in complete graphs with an even number of vertices.

I know that there are implementations that are based on Edmond's celebrated Blossom algorithm available, but they come with some installation over/head/aches I currently don't want to invest.

So, I was wondering, if the Bellman-Ford algorithm couldn't be tweaked to find such optimal matchings.

Surely others may have had the same or a similar idea prior to the publication of Edmond's Blossom algorithm, but had to learn that that doesn't work.

Now I would like to know what the obstructions against using Bellman-Ford for matching problems are; any pointers to articles or counter examples will be highly appreciated.

**An idea for preventing odd negative cycles**

from the answer of user36212 I conclude that the appearing of odd negative cycles is *the* reason why the "ordinary" Bellman-Ford algorithm can fail to report a minimum-weight perfect matching.

Now my idea to rule out negative odd cycles would be to tweak the edge weights prior to applying the Bellman-Ford algorithm to solve the matching problem as described in the **addendum**.

The tweak would be to incorporate edge-counting into shortest-path calculations, which can be done e.g. by adding to each edge-weight a sufficiently large value that is the same for each edge; the effect would be, that a cycle containing $m$ matching edges and $k$ non-matching edges will have non-negative length, whenever $k\ge m$.

If $k=m$ then the added constants are canceled out and it depends only on the original edge weights, whether the sum is negative or not; if the sum is negative, the weight of the matching can be improved by exchanging the roles of the edges on the cycle.

**addendum**

the way I would use the Bellman-Ford algorithm would be to start with an arbitrary perfect matching and then, repeat to negate the weights of the matching-edges, check for negative cycles, exchange on such negative cycles the matching-edges with the non-matching edges, until no more negative cycles are detected.

The question is now, what can go wrong with such an algorithm, whether negative cycles with an odd number of vertices could be reported and/or the running time could be exponential.