Share
Explore BrainMass

C++ Traveller program to find 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

Attached please find the Travel.cpp which contains the program. There are two functions readFileInput() reads the input from datainput.txt (also attached) , determines the number of cities and stores the distances in a two dimensional array.

The second function calculate() does the calculation. The logic is based on iteration. The index for the array 0 - represents the ...

Solution Summary

A classic C++ Traveller program that finds the shortest route given a set of distances between cities. The program uses an input was as source fo data for the cities and distances

$2.19