Traveling Salesman Problem C++ Code Issue
Apr 21, 2017 at 3:03pm UTC
The following code is an algorithm I designed to solve the Traveling Salesman Problem. I am using a Nearest Neighbor Algorithm to find an optimal path and cost of a 5 city tour. When I run the program, the cost calculation is correct. However, the optimal path output is always “154321”. This is the output even if I change the distances between the cities in the cost matrix. How do I configure the code to make the optimal path output change when the distances between the cities are changed in the cost matrix?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
#include <iostream>
using namespace std;
//Global definitions
int costMatrix[5][5];
int vistedCities[5];
int numCity = 5;
int cost = 0;
//Function prototypes
int tsp(int );
void minCost(int );
//Main functions
int main()
{
int i;
int j;
//Enter distance between cities
cout << "\n\nEnter distance between cities into matrix...\n" ;
for (i = 0; i < numCity; i++)
{
cout << "\nEnter " << numCity << " elements in Row[" << i + 1 << "]\n" ;
for (j = 0; j < numCity; j++)
cin >> costMatrix[i][j];
}
//Display matrix of distances between cities
cout << "\nDistances entered into cost matrix:\n" ;
for (i = 0; i < numCity; i++)
{
cout << endl;
for (j = 0; j < numCity; j++)
{
cout << costMatrix[i][j] << " " ;
}
}
//Display results
cout << "\n\n Optimum Path: \t " ;
minCost(0);
cout << "\n Minimum Cost: \t" ;
cout << cost;
system("pause" );
return 0;
}
//Function to determine minimum cost
void minCost(int city)
{
int nearestCity;
vistedCities[city] = 1;
cout << city + 1;
nearestCity = tsp(city);
if (nearestCity == 999)
{
nearestCity = 0;
cout << nearestCity + 1;
cost = cost + costMatrix[city][nearestCity];
return ;
}
minCost(nearestCity);
}
//Funciton for TSP algorithm
int tsp(int city1)
{
int counter;
int nearestCity = 999;
int mini = 999;
int temp;
for (counter = 0; counter < numCity; counter++)
{
if ((costMatrix[city1][counter] != 0) && (vistedCities[counter] == 0))
{
if (costMatrix[city1][counter] < mini)
{
mini = costMatrix[counter][0] + costMatrix[city1][counter];
}
temp = costMatrix[city1][counter];
nearestCity = counter;
}
}
if (mini != 999)
cost = cost + temp;
return nearestCity;
}
Last edited on Apr 21, 2017 at 3:07pm UTC
Topic archived. No new replies allowed.