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

Posted

in

by

Tags: