I'm trying to implement it from wiki but the step 3 confuses me:
- Create a minimum spanning tree T of G.
- Let O be the set of vertices with odd degree in T. By the handshaking lemma, O has an even number of vertices.
- Find a minimum-weight perfect matching M in the induced subgraph given by the vertices from O.
- Combine the edges of M and T to form a connected multigraph H in which each vertex has even degree.
- Form an Eulerian circuit in H.
- Make the circuit found in previous step into a Hamiltonian circuit by skipping repeated vertices (shortcutting).
Induced subgraph I (from odd vertices of O) is taken over G, so it is complete as well as G so there will be multiple perfect matchings.
All Hungarian/Munkres algorithms which I've seen work with Edmonds matrix. To get Edmonds from an arbitrary complete graph I have to 1) split graph into 2 sets of vertices U, V 2) having a split done, perform a minimum matching search in it.
Choosing different sets U, V will give different minimum perfect matchings weight. So the question is how to get a minimum perfect matching in I having a distance matrix of I.