O exercício me pede para imprimir as menores rotas entre n
cidades, considerando que a última é a mesma cidade do ponto inicial. Primeiro, eu preciso ler um arquivo de entrada como o seguinte:
5
1 10
4 4
5 1
2 0
7 21
Onde o primeiro número (5) representa o número de cidades e cada linha abaixo representa cada cidade e suas coordenadas (x,y)
. Cada cidade é representada pela estrutura:
typedef struct
{
int x;
int y;
} Cidade;
Depois, preciso imprimir todas as rotas possíveis e suas distâncias totais, parte que eu também já fiz. Pra isso, eu usei as seguintes funções:
void Troca(int *x, int *y)
{
int aux;
aux = *x;
*x = *y;
*y = aux;
}
void Permuta(FILE *saida, Cidade *C, int *sequencia, int inicio, int
termino, int totalViagens)
{
int i, j;
totalViagens = TotalViagens(termino);
if(inicio == termino)
{
for(i = 0; i < termino; i++)
fprintf(saida, "%d\t", sequencia[i]+1);
fprintf(saida, "= %f\n", Distancia(C, termino, sequencia));
}
else
{
for(j = inicio; j < termino; j++)
{
Troca((sequencia+inicio), (sequencia+j));
Permuta(saida, C, sequencia, inicio+1, termino, totalViagens);
Troca((sequencia+inicio), (sequencia+j));
}
}
}
void CriaSequencia(FILE *saida, Cidade *C, int *sequencia, int numeroCidade)
{
int i;
totalViagens = TotalViagens(numeroCidade);
for(i = 0; i < numeroCidade; i++)
{
sequencia[i] = i;
}
Permuta(saida, C, sequencia, 0, numeroCidade,
TotalViagens(numeroCidade));
}
Com essa funções, o programa imprime em um arquivo de saída essas informações:
120
1 2 3 4 5 = 47.063416
1 2 3 5 4 = 61.486000
1 2 4 3 5 = 46.907471
1 2 4 5 3 = 62.644718
1 2 5 4 3 = 58.522675
1 2 5 3 4 = 57.208015
1 3 2 4 5 = 51.513924
1 3 2 5 4 = 61.814468
1 3 4 2 5 = 47.235947
1 3 4 5 2 = 58.522675
1 3 5 4 2 = 62.644718
1 3 5 2 4 = 61.658531
1 4 3 2 5 = 46.077225
1 4 3 5 2 = 57.208015
1 4 2 3 5 = 50.199272
1 4 2 5 3 = 61.658527
1 4 5 2 3 = 61.814472
1 4 5 3 2 = 61.485996
1 5 3 4 2 = 46.907475
1 5 3 2 4 = 50.199272
1 5 4 3 2 = 47.063412
1 5 4 2 3 = 51.513927
1 5 2 4 3 = 47.235943
1 5 2 3 4 = 46.077229
2 1 3 4 5 = 58.522675
2 1 3 5 4 = 62.644714
2 1 4 3 5 = 57.208019
2 1 4 5 3 = 61.486000
2 1 5 4 3 = 47.063416
2 1 5 3 4 = 46.907475
2 3 1 4 5 = 61.814472
2 3 1 5 4 = 51.513927
2 3 4 1 5 = 46.077225
2 3 4 5 1 = 47.063412
2 3 5 4 1 = 61.485996
2 3 5 1 4 = 50.199272
2 4 3 1 5 = 47.235947
2 4 3 5 1 = 46.907475
2 4 1 3 5 = 61.658527
2 4 1 5 3 = 50.199268
2 4 5 1 3 = 51.513927
2 4 5 3 1 = 62.644714
2 5 3 4 1 = 57.208015
2 5 3 1 4 = 61.658531
2 5 4 3 1 = 58.522675
2 5 4 1 3 = 61.814472
2 5 1 4 3 = 46.077225
2 5 1 3 4 = 47.235947
3 2 1 4 5 = 61.486000
3 2 1 5 4 = 47.063416
3 2 4 1 5 = 50.199272
3 2 4 5 1 = 51.513927
3 2 5 4 1 = 61.814472
3 2 5 1 4 = 46.077225
3 1 2 4 5 = 62.644714
3 1 2 5 4 = 58.522675
3 1 4 2 5 = 61.658531
3 1 4 5 2 = 61.814472
3 1 5 4 2 = 51.513927
3 1 5 2 4 = 47.235947
3 4 1 2 5 = 57.208015
3 4 1 5 2 = 46.077225
3 4 2 1 5 = 46.907471
3 4 2 5 1 = 47.235943
3 4 5 2 1 = 58.522675
3 4 5 1 2 = 47.063412
3 5 1 4 2 = 50.199272
3 5 1 2 4 = 46.907475
3 5 4 1 2 = 61.485996
3 5 4 2 1 = 62.644714
3 5 2 4 1 = 61.658531
3 5 2 1 4 = 57.208015
4 2 3 1 5 = 51.513927
4 2 3 5 1 = 50.199272
4 2 1 3 5 = 62.644714
4 2 1 5 3 = 46.907471
4 2 5 1 3 = 47.235943
4 2 5 3 1 = 61.658527
4 3 2 1 5 = 47.063416
4 3 2 5 1 = 46.077225
4 3 1 2 5 = 58.522675
4 3 1 5 2 = 47.235947
4 3 5 1 2 = 46.907475
4 3 5 2 1 = 57.208015
4 1 3 2 5 = 61.814468
4 1 3 5 2 = 61.658531
4 1 2 3 5 = 61.486000
4 1 2 5 3 = 57.208015
4 1 5 2 3 = 46.077225
4 1 5 3 2 = 50.199272
4 5 3 1 2 = 62.644714
4 5 3 2 1 = 61.485996
4 5 1 3 2 = 51.513927
4 5 1 2 3 = 47.063412
4 5 2 1 3 = 58.522675
4 5 2 3 1 = 61.814472
5 2 3 4 1 = 46.077225
5 2 3 1 4 = 61.814468
5 2 4 3 1 = 47.235947
5 2 4 1 3 = 61.658531
5 2 1 4 3 = 57.208015
5 2 1 3 4 = 58.522675
5 3 2 4 1 = 50.199272
5 3 2 1 4 = 61.486000
5 3 4 2 1 = 46.907471
5 3 4 1 2 = 57.208015
5 3 1 4 2 = 61.658531
5 3 1 2 4 = 62.644714
5 4 3 2 1 = 47.063416
5 4 3 1 2 = 58.522675
5 4 2 3 1 = 51.513924
5 4 2 1 3 = 62.644714
5 4 1 2 3 = 61.486000
5 4 1 3 2 = 61.814472
5 1 3 4 2 = 47.235943
5 1 3 2 4 = 51.513924
5 1 4 3 2 = 46.077225
5 1 4 2 3 = 50.199268
5 1 2 4 3 = 46.907471
5 1 2 3 4 = 47.063416
Onde o primeiro número (120) representa todas as rotas possíveis e cada linha abaixo tem o índice+1 de cada cidade e a distância total da rota. Agora, eu tenho que comparar todas essas distâncias e dizer qual ou quais são as menores, imprimindo a sua rota seguida de sua distância. Lembrando que, caso exista mais de uma rota menor, também preciso imprimir ela. Tentando fazer isso, criei a seguinte função:
float MenorDistancia(FILE *saida, Cidade *C, int numeroCidade, int
totalViagens, int *sequencia)
{
int i;
float menor = INFINITO; //INFINITO = 10000000
for(i = 0; i < totalViagens; i++)
{
if(Distancia(C, numeroCidade, sequencia) <= menor)
menor = Distancia(C, numeroCidade, sequencia);
}
return fprintf(saida, "\nMenor rota: %f\n", menor);
}
E eu mudei a função CriaSequencia
, tentando fazê-la funcionar com a nova função MenorDistancia
.
void CriaSequencia(FILE *saida, Cidade *C, int *sequencia, int numeroCidade,
int totalViagens)
{
int i;
totalViagens = TotalViagens(numeroCidade);
for(i = 0; i < numeroCidade; i++)
{
sequencia[i] = i;
}
Permuta(saida, C, sequencia, 0, numeroCidade,
TotalViagens(numeroCidade));
MenorDistancia(saida, C, numeroCidade, totalViagens, sequencia);
}
Com essas funções, eu tenho o mesmo arquivo de saida mostrado acima, porém, em seu final, eu tenho apenas uma linha
Menor rota: 47.063416
Primeiramente eu gostaria de saber porquê não é mostrada a menor rota, sendo que há rotas menores no arquivo, como podemos ver. E também gostaria de saber uma forma de imprimir as rotas com o índice+1 de cada cidade e, no final, a sua distância total. Lembrando que preciso imprimir todas as menores rotas.
Distancia
? Como foi chamada a funçãoMenorDistancia
para produzir aquele resultado ? Se é uma permutação de cidades, porque asequencia
é umint*
?