# C++ Traveller program finding the shortest route.

Assume you are given a set of N < 10 cities with pairwise distances between them represented as real numbers. A traveler starts from city #1 and wants to visit all other cities just once and return back to the origin. Assume there is a direct airline between any two of these N cities. Your task is to design a C++ program that will find an optimal route for the traveler. That is, the program should return a route of minimum total length. Assuming that the traveler always starts from city 1 the output of the program for N = 4 should be of the form

1 -> 2 -> 4 -> 3 : 226.6

where the last number is the minimum total distance.

Create a file dist.dat for storing the pairwise distances represented as an NxN table of numbers. The number at the intersection of the i-th column and j-th row is the distance from city i to city j. So the table is symmetric; that is, the number at the intersection of row i and column j is the same as the one at the intersection of column i and row j. Note that the number N of cities is not presented explicitly in the file, your program has to figure it out. Your program should read the data from the file by using the input redirection.

Example of such file for N = 4:

56.78 11.80 79.34 78.23

11.80 16.26 65.23 45.19

79.34 65.23 63.29 90.27

78.23 45.19 90.27 87.35

Create your own file for at least 7 cities.

Your program should work for any N in the range [3..10]

#### Solution Preview

...irst city, 1- the second, etc. We always start from city 1, so the we set citiesVisited[0] = 0. And from city 1 we can go to any other city, so in calculate() we have the loop for(int i=1; i<TotalCities; i++). After that the iteration starts with the calc() function, since after going to the next city we can go to any other city again, excluding the cities already visited. ...