Bellman-Ford for Matching Problems? 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.  
 A: This is something like the first step to Edmonds' algorithm.
You certainly need to insist your cycles should be doing something like alternating, otherwise you cannot use this algorithm at all: it won't preserve a matching. Now, in practice to find negative weight alternating cycles, you need to start searching somewhere (this is what Bellman-Ford does) and you will find a problem combinatorially that what you can actually detect is negative weight alternating even circuits, so that the swapping does not work (you have to search two steps at a time to stay alternating, but then Bellman-Ford may give you circuits).
Now the odd cycles you get like this are nothing other than blossoms, you realise that you can get somewhere by contracting them, and you have Edmonds' algorithm.
For concrete counterexamples, assume all your weights are 0 or 1, so that a minimum weight perfect matching is a maximum matching in the weight 0 edges, and the usual examples which show simple searches don't work apply.
Maybe the simplest counterexample to simple searches for maximum matching consists of three triangles plus a vertex sending one edge to each triangle. Here you should find your algorithm doesn't correctly terminate (it will find a maximum matching, but to certify this it should try to augment and detect impossibility; when it tries to augment it either creates something which is not a matching, or gets stuck cycling between two maximum matchings, depending on how you implement it). By contrast, the blossom algorithm, once it has a maximum matching, will sequentially detect the three triangles as blossoms, contract them, and then the remaining graph doesn't have any augmenting walk, so it stops with a certificate - it's this contraction of blossoms that is key, what is basically going on is that simple search can be confused by a blossom, which it 'should' treat as a single vertex but doesn't, while contracting it removes the possibility for confusion.
There are other, faster, maximum matching algorithms, such as Micali-Vazirani, but then you have much more work in implementation (and these are still essentially blossom algorithms).
A: Partial answer for practical approach.
The CAS Leda can compute it, consider checking the references.
From the above link:

MIN_WEIGHT_PERFECT_MATCHING() computes a minimum weighted perfect matching in a general graph. By default the result of the computation is checked internally. This check can be disabled. There is also an explicit check function available. However, using this explicit check functions is quite complicated. For a graph G=(V,E), the running times of computing weighted perfect matchings is O(|V|*|E|log|V|)). The checking functions are linear in the size of the graph. 

The input is C++ program (check the example) and if necessary the C++ graph/weights can be generated from another language and the output.
As far as I can tell, the Leda headers and libraries are free, but the source code might be paid, check the home page for details.
