A salesman wants to go to five different cities and sell some products. The locations of the cities are listed in the following table.
City # X_location Y_location
City 1 1 1
City 2 1 3
City 3 4 1
City 4 5 3
City 5 3 5The distance between two cities is defined as the Euclidean distance. That is:
Distance = sqrt( (x1 – x2)^2 + (y1 – y2)^2 )
For example, the distance between cities 1 and 2 will be:
Distance = sqrt( (1 – 1)^2 + (1 – 3)^2 ) = sqrt( 4 ) = 2The purpose: The salesman starts his journey from city 1. He then has 4 remaining options for the next city (city 2, city 3, city 4, city 5). If he chooses city 3 as the next destination, then he will have 3 remaining options (city 2, city 4, city 5). He wants to travel all the cities and then come back to the start location (City 1). Not all the paths will be a good choice. We want to help the salesman by finding the shortest path (best order of cities to visit (visit all of them once) starting from city 1).Steps:
Step 1 [7 points]: Create a class City with x and y as the class variables. The constructor with argument will get x and y and will initialize the city. Add a member function getDistanceFrom() to the class that gets a city as the input and finds the distance between the two cities.
city1.getDistanceFrom(city2) will be distance between city 1 and 2.Step 2 [6 points]: Create 5 city objects and initialize their location (x and y) using the above table. Then put all of the five cities in a vector.Step 3 [7 points]: Create a two dimensional array or vector DistanceVec of size 5 * 5 and initialize it such that DistanceVec[i,j] is the distance between city_i and city_j. Print the distanceVec and show the distance among all cities.Step 4 [15 points]: If the salesman starts from the city 1, search all the possible paths and find the optimal path (order of cities to visit) that leads to the minimum total travel distance. Display the found optimal path (order of cities to travel) in your sample run.

New Download