Background: I am implementing the nearest neighbor algorithm for the Traveling-Salesman-Problem. I need to calculate the distance traveled for the tour as well as keep track of the order of points visited. I have defined a point class with instance variables x and y and a function calcDist for calculating the distance between two points. I start by storing all of the points in a std::unordered_set named points, creating an empty std::vector named path to store the tour path, and assigning the starting point to startPoint, and pass these to my nearestNeighbor() function:
void nearestNeighbor(unordered_set<Point, PointHasher> points, vector<Point> &path, Point startPoint) {
// Declare variables
unordered_set<Point, PointHasher>::iterator it;
Point currentLocation, possibleNeighbor, nearestNeighbor;
double totalDist = 0;
int pointsCount = path.capacity() - 1;
// Set the starting location
it = points.find(startPoint);
currentLocation = *it;
path[0] = currentLocation;
points.erase(currentLocation);
cout << "Start location: " << path[0].x << ", " << path[0].y << endl;
// Create the path
for (int i = 1; points.size() > 0; i++) {
double minDist = -1;
// Find the current location's nearest neighbor
for (it = points.begin(); it != points.end(); it++) {
possibleNeighbor = *it;
int currentDist = currentLocation.calcDist(possibleNeighbor);
if (minDist == -1 || currentDist < minDist) {
minDist = currentDist;
nearestNeighbor = possibleNeighbor;
}
}
// Record nearest neighbor data and prepare for the next iteration
currentLocation = nearestNeighbor;
path[i] = currentLocation;
points.erase(currentLocation);
totalDist += minDist;
cout << "Nearest neighbor: " << path[i].x << ", " << path[i].y << endl;
}
// Return to the starting location
path[pointsCount] = startPoint;
cout << "End location: " << startPoint.x << ", " << startPoint.y << endl;
cout << "Path:" << endl;
for (int i = 0; i < path.size(); i++) {
cout << path[0].x << ", " << path[0].y << endl;
}
cout << "Total distance: " << totalDist << endl;
}
The problem is that once the program exits the outer for loop, all the points in path are overwritten somehow. To see what I mean, here is the output:
Start location: 3, 4
Nearest neighbor: 6, 8
Nearest neighbor: 11, 7
Nearest neighbor: 50, 8
End location: 3, 4
Path:
3, 4
3, 4
3, 4
3, 4
3, 4
Total distance: 49
Press any key to continue . . .
I am thinking this either has to be a problem with pointers/addresses of the vector elements, or something with scope since the problem happens after exiting the for loop. I have even tried printing the path[1] after each iteration to see when it gets changed, but it is correct throughout the loop, and only changes in the output at the end. Any thoughts? I am stumped. And if you have made it this far, thank you very much for your time.
you are always outputing the coordinates of path[0] man
for (int i = 0; i < path.size(); i++) {
cout << path[0].x << ", " << path[0].y << endl;
}