The exercise asks me to print the smallest routes between n cities, considering that the last one is the same city as the starting point. First, I need to read an input file like the following:
5
1 10
4 4
5 1
2 0
7 21
Where the first number (5) represents the number of cities and each line below represents each city and its (x,y) coordinates. Each city is represented by the structure:
typedef struct
{
int x;
int y;
} Cidade;
Then I need to print out all the possible routes and their total distances, part of which I have already done. For this, I used the following functions:
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));
}
With these functions, the program prints this information in an output file:
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
Where the first number (120) represents all possible routes and each line below has the + 1 index of each city and the total distance of the route. Now, I have to compare all those distances and say which one or which ones are the smaller ones, printing out your route followed by your distance. Remembering that if there is more than one minor route, I also need to print it. Trying to do this, I created the following function:
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);
}
And I changed the function CriaSequencia , trying to make it work with the new function 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);
}
With these functions, I have the same output file shown above, however, at its end, I have only one line
Menor rota: 47.063416
Firstly I would like to know why the smallest route is not shown, and there are smaller routes in the file, as we can see. And I would also like to know a way to print the routes with the index + 1 of each city and, in the end, its total distance. Remembering that I need to print all the smallest routes.