# 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.