The exercise asks me to print, in a file, all possible paths between n
cities, where the end is always the starting point and each city is represented as (x,y)
coordinates. This first part I was able to do, resulting in the following file:
24
(1,10) (4,4) (5,1) (2,0) (1,10)
(1,10) (4,4) (2,0) (5,1) (1,10)
(1,10) (5,1) (4,4) (2,0) (1,10)
(1,10) (5,1) (2,0) (4,4) (1,10)
(1,10) (2,0) (5,1) (4,4) (1,10)
(1,10) (2,0) (4,4) (5,1) (1,10)
(4,4) (1,10) (5,1) (2,0) (4,4)
(4,4) (1,10) (2,0) (5,1) (4,4)
(4,4) (5,1) (1,10) (2,0) (4,4)
(4,4) (5,1) (2,0) (1,10) (4,4)
(4,4) (2,0) (5,1) (1,10) (4,4)
(4,4) (2,0) (1,10) (5,1) (4,4)
(5,1) (4,4) (1,10) (2,0) (5,1)
(5,1) (4,4) (2,0) (1,10) (5,1)
(5,1) (1,10) (4,4) (2,0) (5,1)
(5,1) (1,10) (2,0) (4,4) (5,1)
(5,1) (2,0) (1,10) (4,4) (5,1)
(5,1) (2,0) (4,4) (1,10) (5,1)
(2,0) (4,4) (5,1) (1,10) (2,0)
(2,0) (4,4) (1,10) (5,1) (2,0)
(2,0) (5,1) (4,4) (1,10) (2,0)
(2,0) (5,1) (1,10) (4,4) (2,0)
(2,0) (1,10) (5,1) (4,4) (2,0)
(2,0) (1,10) (4,4) (5,1) (2,0)
Where 24
is the amount of possibilities.
After this first part of the exercise, I have to calculate the smallest possible path, that is, with the shortest distance, using the Euclidean distance formula, and print those paths, and I must do this for each different starting point different initials). For this, I have implemented the following functions:
float Distancia(Cidade cA, Cidade cB)
{
int distanciaX = pow(cA.x - cB.x, 2);
int distanciaY = pow(cA.y - cB.y, 2);
float distancia = sqrt(distanciaX + distanciaY);
return distancia;
}
float Distancias(Cidade *C, int numeroCidades)
{
int i;
float total = 0;
for(i = 0; i < numeroCidades; i++)
{
if(i == numeroCidades - 1)
{
total = total + Distancia(C[i], C[0]);
printf("Distancia: %f\n", Distancia(C[i], C[0]));
}
else
{
total = total + Distancia(C[i], C[i+1]);
printf("Distancia: %f\n", Distancia(C[i], C[i+1]));
}
}
return printf("Distancia Total: %f\n\n", total);
}
I ask the function Distancias
to print the results on the screen to help me initially, because in fact, you need to print them to another file. After these two functions, I used a permutation function (used in another exercise) to print all the possible paths shown above. The function is as follows:
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 i, j;
float distancias[TotalViagens(termino)];
if(inicio == termino)
{
for(i = 0; i < termino; i++)
{
fprintf(saida, "(%d,%d)\t", C[sequencia[i]].x,
C[sequencia[i]].y);
distancias[i] = Distancias(C, termino);
}
fprintf(saida, "(%d,%d)\n", C[sequencia[0]].x, C[sequencia[0]].y);
}
else
{
for(j = inicio; j < termino; j++)
{
Troca((sequencia+inicio), (sequencia+j));
Permuta(saida, C, sequencia, inicio+1, termino);
Troca((sequencia+inicio), (sequencia+j));
}
}
}
Within this same function, I created the variable distancias
to store the values of the distances of all possible trips (considering that the size of the TotalViagens(termino)
vector is calculated by this function). So, I put this vector distancias
in the loop that goes from 0
to the total number of cities that, in the function, is called termino
. I lost some of the logic in the function, but I put it in this loop for the same reason the loop prints all the possible paths, so I guess that, after printing a path, the variable distancias[i]
will get the value returned by function Distancias
. The result I have is the calculation of the same distance every time (96 times for the total of 4 cities and 24 possible paths). The output I have is as follows:
Distancia: 6.708204
Distancia: 3.162278
Distancia: 3.162278
Distancia: 10.000000
.
.
.
That is, the same result is printed 96 times.
I would like to know why the total number of distances is multiplied by the number of cities (24x4) and the possibilities calculated are always the same.