TSP Dynamic Programming

9. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.

#include<stdio.h>
#include<stdlib.h>

int tspdp(int c[10][10], int tour[10], int start, int n);

void main()
{
  int i,j,n,cost,c[10][10], tour[10];
  printf("\n\n*************TSP DYNAMIC PROGRAMMING************\n\n");
  printf("\n\n Enter the number of cities:");
  scanf("%d",&n);
  if(n==1)
  {
        printf("\n Path is not possible\n\n");
        exit(0);
  }
  printf("\n\n Enter the cost matrix\n");
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        scanf("%d",&c[i][j]);
  printf("\n\n The entered cost matrix is\n");
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
      printf("%d\t",c[i][j]);
    }
    printf("\n");
  }
  for(i=1;i<=n;i++)
       tour[i]=i;
  cost=tspdp(c,tour,1,n);
  printf("\n\n The accurate path is \n");
  for(i=1;i<=n;i++)
      printf("%d->",tour[i]);
  printf("1");
  printf("\n\nThe accurate mincost is %d",cost);
  printf("\n\n************ **************** ********** ");
}

int tspdp(int c[10][10], int tour[10], int start, int n)
 {
   int mintour[10],temp[10],mincost=999,ccost,i,j,k;
   if(start==n-1)
    {
      return(c[tour[n-1]][tour[n]]+c[tour[n]][1]);
    }
   for(i=start+1;i<=n;i++)
    {
      for(j=1;j<=n;j++)
               temp[j]=tour[j];
      temp[start+1]=tour[i];
      temp[i]=tour[start+1];
      if((c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<mincost)
       {
          mincost=c[tour[start]][tour[i]]+ccost;
          for(k=1;k<=n;k++)
             mintour[k]=temp[k];
       }
 }
for(i=1;i<=n;i++)
   tour[i]=mintour[i];
return mincost;
}



OUTPUT:

Enter the number of cities:4

Enter the cost matrix
0  1  3  6  1  0  2  3  3  2  0  1  6  3  1  0