Estou realizando a implementação do algoritmo de Christofides e de entrada recebo os dados da TSPLIB. o Algoritmo de Christofides tem os seguintes passos:
- Achar a árvore geradora mínima
- Achar todos os vértices impares (um número par de vértices)
- Achar o casamento mínimo perfeito dos vértices de grau impar
- Adicionar as arestas do casamento perfeito na AGM
- Encontrar um caminho euleriano dentro desse grafo
Eu fui fazendo o algoritmo e cheguei até o passo 5, porém, só ai percebi que o casamento dos vértices que eu estava encontrando não era o perfeito, que é feito nesse código a seguir:
int** adicionar_CM_na_AGM(int **m, int **agm, int qVgi, int *vGi,int n){
int menor =99999,v1=0,v2=0,verticeMenor;
int *aux = (int *) calloc(qVgi, sizeof(int));
for(int i=0; i<qVgi; i++)
{
for(int j=0; j<qVgi; j++)
{
if(vGi[i] != vGi[j] && menor > m[vGi[i]][vGi[j]] && aux[vGi[i]] != 1 && aux[vGi[j]] != 1)
{
printf("%d O %d\n", i, m[vGi[i]][vGi[j]]);
v1 = vGi[i];
v2 = vGi[j];
menor = m[vGi[i]][vGi[j]];
}
}
aux[v1]= 1;//cria a situação de já visitados
aux[v2]= 1;
agm[v1][v2] = m[v1][v2];//adiciona na AGM as arestas dos vGi
agm[v2][v1] = m[v2][v1];
menor =9999;
}
return agm;
sendo : m: matriz de adjacência com as distâncias dos vértices
agm: matriz de adjacência da AGM de m
qVgi: inteiro que representa a quantidade de vértices de grau impar
vGi: vetor que contém os números dos vértices que tem grau impar
n: inteiro que representa o número de vértices total da matriz m
Gostaria de saber se alguém teria ideias para que eu consiga achar o casamento mínimo perfeito dos vértices de grau impar do meu grafo.