TSP

#include<iostream>
#include<conio.h>
int s,c[100][100],ver;
float optimum=999,sum;

using namespace std;

/* function to swap array elements */
void swap(int v[], int i, int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}


/* recursive function to generate permutations */
void brute_force(int v[], int n, int i)
{
// this function generates the permutations of the array from element i to element n-1
int j,sum1,k;
//if we are at the end of the array, we have one permutation
if (i == n)
{
if(v[0]==s)
{
for (j=0; j<n; j++)
cout<<"  "<<v[j];
sum1=0;
for( k=0;k<n-1;k++)
{
sum1=sum1+c[v[k]][v[k+1]];
}
sum1=sum1+c[v[n-1]][s];
cout<<" sum ="<<sum1<<endl;
getch();
if (sum1<optimum)
optimum=sum1;
}
}
else
// recursively explore the permutations starting at index i going through index n-1*/
for (j=i; j<n; j++)
{ /* try the array with i and j switched */
swap (v, i, j);
brute_force (v, n, i+1);
/* swap them back the way they were */
swap (v, i, j);
}
}

void nearest_neighbour(int ver)
{
int min,p,i,j,vis[20],from;
for(i=1;i<=ver;i++)
vis[i]=0;
vis[s]=1;
from=s;
sum=0;
for(j=1;j<ver;j++)
{
min=999;
for(i=1;i<=ver;i++)
if(vis[i] !=1 &&c[from][i]<min && c[from][i] !=0 )
{
min= c[from][i];
p=i;
}
vis[p]=1;
from=p;
sum=sum+min;
}
sum=sum+c[from][s];
}

void main()
{
int ver,v[100],i,j;
//clrscr();
cout<<"Enter the value of n : ";
cin>>ver;
for (i=0; i<ver; i++)
v[i] = i+1;
cout<<"Enter cost matrix\n";
for(i=1;i<=ver;i++)
for(j=1;j<=ver;j++)
cin>>c[i][j];

cout<<"\nEnter source : ";
cin>>s;
brute_force (v, ver, 0);
cout<<"\nOptimum solution with brute force technique is="<<optimum;
nearest_neighbour(ver);
cout<<"\nSolution with nearest neighbour technique is="<<sum;
int temp=((sum/optimum)-1)*100;
cout<<"\nThe approximation val is="<<temp;
cout<<" % ";
getch();
}