 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Traveling Salesman Problem C++ Code Issue

1. Junior Member Join Date
Oct 2016
Posts
9

## Traveling Salesman Problem C++ Code Issue

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?

Code:
```#include <iostream>
using namespace std;

//Global definitions
int costMatrix;
int vistedCities;
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] + costMatrix[city1][counter];
}
temp = costMatrix[city1][counter];
nearestCity = counter;
}
}
if (mini != 999)
cost = cost + temp;

return nearestCity;
}```  Reply With Quote

2. ## Re: Traveling Salesman Problem C++ Code Issue

Did you try to debug your code to see where, how, and why goes wrong?  Reply With Quote

3. Junior Member Join Date
Oct 2016
Posts
9

## Re: Traveling Salesman Problem C++ Code Issue

Yes, I tried to debug the code, but I honestly could not figure it out. Whenever I change the code to loop through the possible permutations, I get a stack space overflow error message, and the program crashes.  Reply With Quote

4. ## Re: Traveling Salesman Problem C++ Code Issue

Then try to debug again. Particularly your function void minCost(int city) seems to need being debugged!
And BTW, why are so sure that the nearestCity will be (and not too late!) exactly 999?  Reply With Quote

5. ## Re: Traveling Salesman Problem C++ Code Issue

I agree with Victor, in these circumstances you need to use the debugger to trace through the code - line by line if needed - to see what is happening and where the execution deviates from that expected from the program design.

I get a stack space overflow error message, and the program crashes
minCost() function is recursive. A stack space overflow error message usually indicates that there is a problem with the recursion terminating condition and that the terminating condition is not being met. In this case recursion only stops when tsp(city) returns 999 ??  Reply With Quote

6. Junior Member Join Date
Oct 2016
Posts
9

## Re: Traveling Salesman Problem C++ Code Issue

Thanks for the advice, I am looking into it.  Reply With Quote

algorithms, c++ #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 