TSP Approximation Algorithm

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>

void tspapp(int v);

int visited[10],city,cost[10][10],count,mincost,i,j;

void main()
{
  printf("\n\n******TSP APPROXIMATION PROBLEM**\n\n");
  printf("Enter the number of cities:");
  scanf("%d",&city);
  printf("\n\nEnter the cost matrix\n\n");
  for(i=1;i<=city;i++)
   {
      for(j=1;j<=city;j++)
       {
          scanf("%d",&cost[i][j]);
       }
   }
  printf("\n\n The entered cost matrix is \n");
  for(i=1;i<=city;i++)
   {
      for(j=1;j<=city;j++)
       {
          printf("%d\t",cost[i][j]);
       }
       printf("\n");
   }
  printf("\n\n The approximate path is \n");
  tspapp(1);
  printf("\n\n************* **************** ************\n");
}

void tspapp(int v)
{
  int k,min;
  visited[v]=1;
  printf("%d->",v);
  if(count==city-1)
   {
     mincost=mincost+cost[v][1];
     printf("1");
     printf("\n\nApproximate Mincost is %d",mincost);
     return;
   }
  min=999;
  for(j=1;j<=city;j++)
   {
     if(cost[v][j]<min&&cost[v][j]!=0&&!visited[j])
      {
         min=cost[v][j];
         k=j;
      }
   }
  mincost=mincost+cost[v][k];
  count++;
  tspapp(k);
}



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