What is the traveling salesman problem?
Introduction
The traveling salesman problem is as follows:
A salesman has to start their journey from one city and visit all the cities at least once before returning to the initial city. They want to choose the path that has the smallest path distance. The distance from city A to city B can differ from the distance from city B to city A. The permutations of all the cities will be calculated. We have to find the path with the smallest path length.
Algorithm
The main goal is to find the smallest path length.
- Let’s suppose city A is the starting and the ending city. The objective is to find the cyclic path and consider any city as a starting city.
- We have
n—the number of cities. Therefore, we generate all the(n-1)!permutations of the cities. - After finding the permutations of all cities, we calculate the path length of each permutation and remember the minimum path length permutation.
- We return the permutation/path with the minimum path length.
Example
Suppose that Node A is the starting city, and the salesman starts their journey from this city, selects the smallest path, and returns to Node A.
This table shows the distance between the cities.
TSP Distance Table
City | A | B | C | D |
A | 0 | 4 | 1 | 3 |
B | 4 | 0 | 2 | 1 |
C | 1 | 2 | 0 | 5 |
D | 3 | 1 | 5 | 0 |
Example
The following code takes a 2-D array of distances of cities as mentioned in the table. It then prints the shortest path and returns the smallest path length from all possible path lengths:
// C Plus Plus program to solve traveling salesman problem#include <bits/stdc++.h>using namespace std;#define V 4/*This Function gets 2d array in which we have distancesfrom one city to another city and gets starting cityas well*/int traveling_Salesman_Problem(int distance[][V], int starting_city){// store all vertex apart from source vertexvector<int> vertex,vertex1;for (int i = 0; i < V; i++){if (i != starting_city){vertex.push_back(i);}}// store minimum weight Hamiltonian Cycle/Path.// Hamiltonian is like we have A->B->C->D->A, its a Cycle and its called Hamiltonian cycleint minimum_path_length = 100000;//max valuewhile (next_permutation(vertex.begin(), vertex.end())){// store current Path Lenght(cost)int current_path_length = 0;// compute current path lengthint val = starting_city;for (int i = 0; i < vertex.size(); i++) {current_path_length += distance[val][vertex[i]];val = vertex[i];}current_path_length += distance[val][starting_city];// Update Minimum Path Length if we found minimum length// minimum_path_length = min(minimum_path_length, current_path_length);if(minimum_path_length>current_path_length){minimum_path_length=current_path_length;vertex1.clear();for (int i = 0; i < vertex.size(); i++) {vertex1.push_back(vertex[i]);}}}cout<<"Shortest-Path : "<<starting_city<<"->";for (int i = 0; i < V; i++){cout<<vertex1[i]<<"->";}cout<<"\n";return minimum_path_length;}int main(){// 2-D array representation of Distances Between Citiesint distance[][V] = { { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };int starting_city = 0;//City Acout <<"Minimum Path Length will be : "<< traveling_Salesman_Problem(distance, starting_city) << endl;return 0;}
Explanation
- Line 4: We define a value for the number of cities.
- Lines 9–52: We define the
traveling_Salesman_Problemfunction that takes thedistancesand thestarting city. - Lines 13–17: We add all the cities in a
vertexthat are not the starting cities. - Line 20: We define a minimum distance variable as a maximum value.
- Lines 22–45: We go through all the permutations and save the shortest distance path in
vertex1. - Lines 46–49: We print the shortest distance path.
- Lines 58–61: We define the 2-D array for distances between cities.
- Line 62: We define the starting city.
- Line 63: We call the function to calculate the shortest path between the cities.
