C program of Travelling Salesman Problem

C program of Travelling Salesman Problem

5118
10
SHARE

C program of Travelling Salesman Problem : The Travelling salesman problem (TSP) is an NP-hard problem. NP-hard problem is a class of problems that are, informally, “at least as hard as the hardest problems in NP” or you can simply say solution to problem cannot be generalized i.e. We may not have optimal solution every time.

I have tried to find the solution using operational search technique but its not always optimal. :D Its not mine approach, all the approaches for this problem cannot guarantee an optimal solution every time but i can simply say it will going to be the best approach for solving Travelling salesman problem other than approach, genetic algorithm and dynamic programming.

Algorithm to solve Travelling Salesman Problem :

1. Prepare a cost to calculate the weights . If the entered cost matrix is not a square matrix then add a new column with zero cost element.
2. Determine the minimum element in each row and subtract the minimum element in each row from all the elements of the respective rows.
3. Now we have a resulting matrix. Now repeat the same process of step 2 for all the columns i.e. determine the minimum element in each column and subtract that minimum value from all  elements of their respective column to obtain new resulting matrix.

4. Now after row and column operations, draw minimum number of horizontal and vertical lines to cover all zeros in resulting matrix. Let a be the minimum number of lines  and n is the order of matrix.

Then two possible scenarios can happen :
4.1  If a=n,then an optimal assignment of paths can be done.
4.2 If N<n,then proceed.

5. Now find smallest uncovered element in the matrix by “a” lines.

6. Subtract the minimum element obtained in step 5 from all uncovered elements and add the same elements at the intersection of horizontal and vertical lines to obtain intermediate matrix.
7. Repeat step(2) to step (4) until we get the case 4.1 .
8.  (For making zero assignments) Examine the rows successively row by row until single zero is found. Circle this zero to make the assignment and then mark a cross(x) over all zeros if its lying in the column of the circled zero, showing that they can’t be considered for future assignment. Continue in this manner until all the zeros have been examined.
Repeat the same procedure for columns also.
9. Repeat the step 7 successively until one of the below condition arises :
(i) If  no unmarked zeros is left,then the process ends
(ii) If there lies more than one of the unmarked zero in any column or row then, circle one of the unmarked zeros arbitrarily and mark a cross in the cell of remaining zeros in its row or column and repeat the process until no unmarked zero is left in the matrix.
10 :- Thus exactly one marked circled zero in each row and each column of the matrix is obtained and hence assignment corresponding to these marked circle zeros will give the optimal assignment.

That ends the algorithm for Travelling Salesman Problem. Now lets see .

Note : If any of the two rows in cost matrix are same below program will not produce an optimal solution.

C program of Travelling Salesman Problem Solution :

#include<stdio.h>
#include<conio.h>
int main()
{ 
  int cost[20][20],min,l,m,sr[20],sc[20],flag[20][20],i,j,k,rf[20],cf[20],n;
  int nrz[20],ncz[20],cn,a,noz,nrz1[20],ncz1[20],counter =0;
  printf("-----------------------------------------------------------\n");
  printf("----------------------Made by C code champ-----------------\n");
  printf("-----------------------------------------------------------\n\n");
  printf("\n\tC PROGRAM FOR TRAVELLING SALESMAN PROBLEM");
  printf("\n\nEnter the total number of assignments:");
  scanf("%d",&n);
  /* Enter the cost matrix*/
  printf("\nEnter the cost matrix\n");
  for(i=0;i<n;i++)
  { 
     printf("\n");
     for(j=0;j<n;j++)
     {
       printf("cost[%d][%d] = ",i,j);
       scanf("%d",&cost[i][j]);
      }
  }
  printf("\n\n");
  /* Display the entered cost matrix*/
  printf("Cost matrix:\n");
  for(i=0;i<n;i++)
  { 
     for(j=0;j<n;j++)
      printf("\t%d\t",cost[i][j]);
      printf("\n");
  }
  /* operation on rows*/
  for(i=0;i<n;i++)
  { 
    min=cost[i][0];
    /* find the minmum element in each row*/
    for(j=0;j<n;j++)
    { 
       if(min>cost[i][j])
       min=cost[i][j];
    }
    /*subtract the minimum element from each element of the respective rows*/
    for(j=0;j<n;j++)
     cost[i][j]=cost[i][j]-min;
  }
  /* operation on colums*/
  for(i=0;i<n;i++)
  {
    min=cost[0][i];
    /* find the minimum element in each column*/ 
    for(j=0;j<n;j++)
    { 
     if(min>cost[j][i])
       min=cost[j][i];
    }
    /*subtract the minimum element from each element of the respective columns*/
    for(j=0;j<n;j++)
     cost[j][i]=cost[j][i]-min;
  }
  printf("\n\n");
  printf("Cost matrix after row & column operation:\n");
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     printf("\t%d\t",cost[i][j]);
    printf("\n");
  }
  repeatx:;
  /*Draw minimum number of horizontal and vertical lines to cover all zeros in 
  resulting matrix*/ 
  a=0;noz=0,min=1000;
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
     flag[i][j]=0;
  }
  for(i=0;i<n;i++)
  { cn=0;
    for(j=0;j<n;j++)
    { if(cost[i][j]==0)
      { cn++;
    flag[i][j]=1;
      }
    }
    nrz[i]=cn;
    noz=noz+cn;
  }
  for(i=0;i<n;i++)
  { cn=0;
    for(j=0;j<n;j++)
    { if(cost[j][i]==0)
      { cn++;
    flag[j][i]=1;
      }
    }
    ncz[i]=cn;
    noz=noz+cn;
  }
  for(i=0;i<n;i++)
  { nrz1[i]=nrz[i];
    ncz1[i]=ncz[i];
  }
  k=0;
  while(nrz[k]!=0||ncz[k]!=0)
  {
  for(i=0;i<n;i++)
   { cn=0;
    for(j=0;j<n;j++)
    { if(flag[i][j]==1)
       cn++;
      nrz[i]=cn;
    }
    if(nrz[i]==1)
    { for(j=0;j<n;j++)
      { if(flag[i][j]==1)
    { flag[i][j]=2;
      for(k=0;k<n;k++)
      { if(flag[k][j]==1)
         flag[k][j]=0;
      }
    }
      }
    }
  }
  for(i=0;i<n;i++)
  { cn=0;
    for(j=0;j<n;j++)
    { if(flag[j][i]==1)
       cn++;
      ncz[i]=cn;
    }
    if(ncz[i]==1)
    { for(j=0;j<n;j++)
      { if(flag[j][i]==1)
    { flag[j][i]=2;
      for(k=0;k<n;k++)
      { if(flag[j][k]==1)
         flag[j][k]=0;
      }
    }
      }
    }
  }
  k++;
 }
  for(i=0;i<n;i++)
  { for(j=0;j<n;j++)
    { if(flag[i][j]==2)
    a++;
    }
  }

  /* If minimum number of lines, a is equal to the order of the matrix n then 
  assignment can be optimally completed.*/
  if(a==n)
  { 
    printf("\nAssignments completed in order!!\n");
    /* Display the order in which assignments will be completed*/
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(flag[i][j]==2)
      printf(" %d->%d ",i+1,j+1);
      }
      printf("\n");
    }
    getch();
    exit(0);    
  }
  /* if order of matrix and number of lines is not same then its difficult to 
  find the optimal solution.
  Now determine the smallest uncovered element i.e. element not covered by lines
  and then subtract this minimum element from all uncovered elements and add the 
  same elements at the intersection of horizontal and vertical lines.*/
  else
  { for(i=0;i<n;i++)
    { rf[i]=0,sr[i]=0;
      cf[i]=0,sc[i]=0;
    }
    for(k=n;(k>0&&noz!=0);k--)
    { for(i=0;i<n;i++)
      { m=0;
    for(j=0;j<n;j++)
    { if((flag[i][j]==4)&&(cost[i][j]==0))
       m++;
    }
        sr[i]=m;
      }
      for(i=0;i<n;i++)
      { if(nrz1[i]==k&&nrz1[i]!=sr[i])
    {  rf[i]=1;
       for(j=0;j<n;j++)
       { if(cost[i][j]==0)
           flag[i][j]=4;
       }
       noz=noz-k;
    }
      }
      for(i=0;i<n;i++)
      { 
      l=0;
      for(j=0;j<n;j++)
      { if((flag[j][i]==4)&&(cost[j][i]==0))
       l++;
      }
        sc[i]=l;
      }
      for(i=0;i<n;i++)
      { if(ncz1[i]==k&&ncz1[i]!=sc[i])
    {  cf[i]=1;
       for(j=0;j<n;j++)
       { if(cost[j][i]==0)
           flag[j][i]=4;
       }
       noz=noz-k;
    }
      }
      for(i=0;i<n;i++)
      { for(j=0;j<n;j++)
    { if(flag[i][j]!=3)
      { if(rf[i]==1&&cf[j]==1)
        {  flag[i][j]=3;
           if(cost[i][j]==0)
         noz=noz+1;
        }
      }
    }
      }
    }
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(rf[i]!=1&&cf[j]!=1)
    { if(min>cost[i][j])
        min=cost[i][j];
    }
      }
    }
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(rf[i]!=1&&cf[j]!=1)
      cost[i][j]=cost[i][j]-min;
      }
    }
    for(i=0;i<n;i++)
    { for(j=0;j<n;j++)
      { if(flag[i][j]==3)
      cost[i][j]=cost[i][j]+min;
      }
    }
  }
  printf("\n\n");
  if (counter < 10)
  {
   counter = counter+1;  
  printf("\n\nIntermediate Matrix: \n");
  for(i=0;i<n;i++)
  {            
    for(j=0;j<n;j++)
    printf("\t%d\t",cost[i][j]);
    printf("\n");
  }
  }
  else
  {
      printf("\n\nOptimal solution to given problem is not possible");
      getch();
      return 0;
      }
  goto repeatx;
}

We hope you all have enjoyed the solution. I will write another code using dynamic programming for travelling salesman problem which is quite optimal.

If you have any queries regarding the code, ask us in form of comments.

 

10 COMMENTS

  1. Your articles were so good. After browsing your blog???I have benefited greatly~~~~Hope you can create more splendid works~~ have a good content of articles~~~so that we can often browse them~~~~.

  2. I just want to say I am just beginner to weblog and really savored your web site. Most likely I’m planning to bookmark your blog post . You surely have beneficial stories. Bless you for revealing your blog.

  3. Hi,

    Was really enthralled after reading your blog n d codes…
    I am trying to build a code for Travelling Salesman Problem with dynamic allocation with the minimum distance traveled by the person. Can you help me out on that.
    Regards
    subho

  4. Hi, i am an Mtech (CSE) student doing my project in TSP using GA. i need your help. please give me your email id so that i can contact you.

  5. I am working on material flow optimisation problem. I need to prepare a code of genetic algorithm optimisation method in c programming . can you help me in preparing the same

LEAVE A REPLY