TRAVELLING SALESMAN PROBLEM

TRAVELLING SALESMAN PROBLEM

#include”iostream.h”
#include”conio.h”
int n,a[50][50],bpath[50],list[50],i,j,bcost,tbcost;
void calculate(int list[])
{
int t;
tbcost=0;
for(j=1;j {
t=a[list[j-1]][list[j]];
if(t!=0)
tbcost+=a[list[j-1]][list[j]];
else
tbcost=bcost+1;
}
}

void snap(int &x, int &y)
{
int temp;
temp=x;
x=y;
y=temp;
}

void permute(int k, int x)
{
int temp,i,j;
if(k==x)
{
calculate(list);
if(bcost==0)
bcost=tbcost+1;
if((tbcost {
bcost=tbcost;
for(j=0;j bpath[j]=list[j];
}
}
else
{
for(i=k;i<=x;i++)
{
snap(list[k],list[i]);
permute(k+1,x);
snap(list[k],list[i]);
}
}
}

void main()
{
clrscr();
cout<<"Enter the number of cities\n";
cin>>n;
for(i=0;i for(j=0;j {
if(i!=j)
{
cout<<"\nEnter the cost of travelling from"<<"("< cin>>a[i][j];
}
else
a[i][j]=0;
}
for(i=0;i list[i]=i;
permute(1,n-1);
cout<<"\nBest path is\n\n";
for(i=0;i cout< cout<<"\n\n Cost of best path is: "<< bcost+a[bpath[n-1]][0];
getch();
}





Enter the number of cities
4
Enter the cost of travelling from(1to2)6

Enter the cost of travelling from(1to3)0

Enter the cost of travelling from(1to4)8

Enter the cost of travelling from(2to1)4

Enter the cost of travelling from(2to3)3

Enter the cost of travelling from(2to4)0

Enter the cost of travelling from(3to1)0

Enter the cost of travelling from(3to2)5

Enter the cost of travelling from(3to4)10

Enter the cost of travelling from(4to1)2

Enter the cost of travelling from(4to2)0

Enter the cost of travelling from(4to3)6

Best path is

1 2 3 4

Cost of best path is: 21