I am creating Christofides algorithm for the Traveling Salesman Problem. In part of the algorithm I need to find nodes of a graph that are of odd degree and then calculate the lowest weight. This can be done by the Blossom algorithm, but I am choosing to do it a different way by finding the sum of the possible combinations that you have from a 2D array because I am struggling with the blossom algorithm and do not understand it.
I have 2D array which stores the weights between vertices of odd degree in a graph. For example:
$array = array(
0=> array(0, 2, 20,4),
1=> array(2,0,7,8),
2=> array(20,2,0,12),
3=> array(4,8,12,0)
)
so between 0 and 1 is of weight 2, if i select the vertices 0 and 1, I am then left with the weight between vertex 2 and 3 because vertex 0 and 1 has already been used. I then need to sum the weights of array[0][1] and array[2][3].
I am struggling with creating an algorithm that returns the combination of possible vertex pairs. For example in the array above the possible pairs are [(0,1)(2,3)],[(0,2)(1,3)],[(0,3)(1,2)]
(0,0),(1,1),(2,2),(3,3) cannot be used as there is no edge weight between them. Also, the reverse of them is not needed([(1,0)(2,3)]).
With these pairs I can then calculate the sum of the weights and choose the smallest.
Any help would be much appreciated.