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.

  1. 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.
  2. We have n—the number of cities. Therefore, we generate all the (n-1)! permutations of the cities.
  3. After finding the permutations of all cities, we calculate the path length of each permutation and remember the minimum path length permutation.
  4. 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.

g A A B B A->B C C A->C D D A->D B->A B->C B->D C->A C->B C->D D->A D->B D->C
TSP Graph

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 distances
from one city to another city and gets starting city 
as well
*/
int traveling_Salesman_Problem(int distance[][V], int starting_city)
{
    // store all vertex apart from source vertex
    vector<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 cycle
    int minimum_path_length = 100000;//max value
     while (next_permutation(vertex.begin(), vertex.end()))
     {
        // store current Path Lenght(cost)
        int current_path_length = 0;
 
        // compute current path length
        int 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 Cities
    int distance[][V] = { { 0, 4, 1, 3 },
                       { 4, 0, 2, 1 },
                       { 1, 2, 0, 5 },
                       { 3, 1, 5, 0 } };
    int starting_city = 0;//City A
    cout <<"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_Problem function that takes the distances and the starting city.
  • Lines 13–17: We add all the cities in a vertex that 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.

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)