write travelling salesman problem solution with example in c++
Here’s an example of solving the Traveling Salesman Problem (TSP) using the Nearest Neighbor Algorithm in C++:
#include <iostream>
#include <vector>
#include <limits>
const int INF = std::numeric_limits<int>::max();
// Function to find the nearest unvisited city from the given current city
int findNearestCity(int currentCity, const std::vector<bool>& visited, const std::vector<std::vector<int>>& graph) {
int nearestCity = -1;
int minDistance = INF;
for (int i = 0; i < graph.size(); ++i) {
if (!visited[i] && graph[currentCity][i] < minDistance) {
minDistance = graph[currentCity][i];
nearestCity = i;
}
}
return nearestCity;
}
// Function to solve the TSP using the Nearest Neighbor Algorithm
std::vector<int> solveTSP(const std::vector<std::vector<int>>& graph) {
int numCities = graph.size();
std::vector<bool> visited(numCities, false);
std::vector<int> route(numCities);
// Start from the first city
int currentCity = 0;
visited[currentCity] = true;
route[0] = currentCity;
// Find the nearest unvisited city and add it to the route
for (int i = 1; i < numCities; ++i) {
int nearestCity = findNearestCity(currentCity, visited, graph);
route[i] = nearestCity;
visited[nearestCity] = true;
currentCity = nearestCity;
}
return route;
}
int main() {
std::vector<std::vector<int>> graph = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
std::vector<int> optimalRoute = solveTSP(graph);
std::cout << "Optimal Route: ";
for (int city : optimalRoute)
std::cout << city << " ";
std::cout << "0n";
int optimalDistance = 0;
for (int i = 0; i < optimalRoute.size() - 1; ++i)
optimalDistance += graph[optimalRoute[i]][optimalRoute[i + 1]];
std::cout << "Optimal Distance: " << optimalDistance << std::endl;
return 0;
}
In this example, we have a graph representing the distances between cities. The findNearestCity function finds the nearest unvisited city from the current city based on the distance matrix. The solveTSP function uses the Nearest Neighbor Algorithm to construct the TSP route by iteratively selecting the nearest unvisited city until all cities are visited.
In the main function, we define a graph with distances between four cities. We call the solveTSP function to obtain the optimal route and then calculate and display the optimal distance.
The Nearest Neighbor Algorithm provides a simple and efficient approach to approximate solutions for the TSP, but it may not always yield the optimal solution.
