“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”.
Suppose we have three cities A, B and C. So by distance matrix api we will get distances of A-A, A-B, A-C, B-B, B-A, B-C, C-A, C-B, C-C. I will thank google for this. Now I will create a matrix of the distances, like this:
|[A-A A-B A-C]| |[0 A-B A-C]|
|[B-A B-B B-C]| = |[B-A 0 B-C]|
|[C-A C-B C-C]| |[C-A C-B 0]|
Just check that the distance from A-B and B-A are not equal because it is the distance related to road. It’s not necessary that the path for A-B will be same for B-A that’s why distances are not equal. So going ahead I will calculate the permutations of all the cities and will store it in an array, like this:
I will name city A as 1, B as 2 and C as 3.
then the permutations will be
and I append “1” at the front and at the end of each permutation. So now our new permutation array will become like this:
[1,1,2,3,1] -> So it will be 1 to 1 to 2 to 3 to 1
After this, I will proceed with the mapping of these permutations and the distance matrix which we created above. So by doing this I will calculate all the distances related to every permutation and the permutation with shortest distance will be your shortest route.
You are fully welcome to state your own views and comments and if this helped you then I will be touched. 🙂