Printing the shortest distances

Question

The exercise asks me to print the smallest routes between n cities, whereas the latter 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 row below represents each city and its coordinates (x,y). Each city is represented by the structure:

typedef struct
{
    int x;
    int y;
} Cidade;

Then, I need to print all possible routes and their total distances, part that I also did. 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 this function, the program prints in an output file this information:

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 row below has the index+1 of each city and the total distance of the route. Now, I have to compare all these distances and say which or which ones are the smallest, printing their route followed from their distance. Remember 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

First 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 how to print the routes with the+1 index of each city and, in the end, their total distance. Remembering that I need to print out all the smaller routes.

Answer 1

If the items are in a array you can do so.

Iterate over all items and then check them one by one. I don’t know much about c so I’ll make one pseudo code for you

double menorvalor = 10000000;
for(int i = 0;i < lista.Tamanho;i++) //iteração sobre todos os itens
{
    if (lista[i] < menorvalor)//toda vez que o valor for menor ele vai ser setado como o menor sendo o menor setado primeiramente um valor absurdo.
    {
        menorvalor = lista[i];
    }
}

this would work, if that’s what you wanted is just adapt to the c.

From what I saw in your code it seems to me that you compare to the wrong values.

for (i = 0; i < totalViagens; i++)

shouldn’t be the total distances?

at last I may be traveling but...

Now if you want a list of lower values just do the same iteration only using an array x (where x is the number of lower values you want) and compare with the list Ex

float[] listamenor = float[x]; //lista de x menores valores.
float menorvalor = 10000000;
for(int i = 0;i < listamenor.Tamanho;i++)
{
listamenor[i] = 0; //setando todos os valores a 0.
}

for(int i = 0;i < lista.Tamanho;i++) //iteração sobre todos os itens
{
    if (lista[i] < listamenor[0])// vamos supor que a lista é de 2 menores numeros
    {
        listamenor[0] = lista[i];
    }
    else if (lista[i] < listamenor[1])
//isso é uma má pratica mas você pode fazer usando o for para comparar todos os itens da listamenor.
    {
        listamenor[1] = lista[i];
    }
}

Good luck.