The Travelling Salesman Problem (Exhaustive Approach)

For those of you who don’t know what this problem is about, here is the problem statement:
You are given a list of cities and the distances between all connected cities. Find the shortest path that visits each city exactly once and returns to the origin city. 

To approach this problem using exhaustive search, we need all permutations of the cities and find out which path through them is the shortest. Here is my approach, using the next_permutation() function:

#include <iostream>
#include<algorithm>
using namespace std;

char nodes[]={‘A’,’B’,’C’,’D’,’E’}; //names of cities
int node[]={0,1,2,3,4,5}; //to permute numbers
int cities=5;                    //change this number for more or less cities
int distance_mat[10][10]; // the distance matrix from city[i] to city[j]

int min_cost=10000;   //arbitrary large value which will be replaced
char min_path[6];

//take distance input in the form of a matrix

void createGraph()
{
cout<<“\tA\tB\tC\tD\tE\n”;
for(int i=0;i<cities;i++)
{
cout<<nodes[i]<<“\t”;
for(int j=0;j<cities;j++)
{
cin>>distance_mat[i][j];
}
}
}

int shortest(int a,int b)     //find a path from the last visited city to the origin city
{
static int cost=0;
if(distance_mat[a][b]!=0)
return distance_mat[a][b];

for(int j=0;j<cities;j++)
if(distance_mat[a][j]!=0)
return cost+=distance_mat[a][j]+shortest(j,b);
}

void findcost()   //calculate cost/distance
{
int cost=0,cnt=1;
char path[6];
path[0]=nodes[node[0]];
for(int i=0,j=1;j<cities;i++,j++)
{
if(distance_mat[node[i]][node[j]]!=0)
{
path[cnt++]=nodes[node[j]];
cost+=distance_mat[node[i]][node[j]];
}
}
if(cnt<cities)
return;
cost+=shortest(node[cities-1],node[0]);
path[cnt++]=nodes[node[0]];

if(cost<min_cost)
{
min_cost=cost;
for(int i=0;i<cities+1;i++)
{
min_path[i]=path[i];
}
}
}

int main()
{

cout<<“Create Graph\n\n”;

createGraph();
do{
findcost();
}while(next_permutation(node,node+cities));  //will generate all permutations. In-built function in algorithm.h

cout<<“Minimum distance: “<<min_cost<<endl;
cout<<“Path Followed: “;
for(int i=0;i<cities+1;i++)
{
cout<<min_path[i]<<“\t”;
}
cout<<endl;
return 0;
}