Is there an algorithm for computing permutation of distances?

Question

This is related to travelling salesman problem. First all permutations need to be generated and then the destination (same as origin) attached. I.e.: 1) abcd abdc ....

2) abcda abdca ....a

I have all the distances and only need an algorithm to sum them up. I wonder if there is an algorithm (C preferable) I can use for this or if there is a ready-made solution somewhere.

Answer 1

This is kinda trivial.

int sum = 0;
for (i = 0; i < length-1; i++)
{
  sum += distance[group[i]][group[i+1]];
}

Where distance is a 2d array (matrix if you will) that holds the distance between the two nodes. group should be an array or vector or the nodes in order traveled.

If you also need to get each permutation, use next_permutation.

Here's a brief example of what distance might be:

int distance[4][4] = {
 {0,2,1,0},
 {2,0,1,2},
 {1,1,0,1},
 {0,2,1,0},
};

Note that this will be a symmetric matrix for your problem.