Answer to Question #230802 in C for Sky

Question

Write a c code for travelling salesman problem using brute force.

Answer 1

#include<stdio.h>
 
int arr[10][10],comp[10],n,cost=0;
 
void get_input()
{
int i,j;
 
printf("Enter number of villages: ");
scanf("%d",&n);
 
printf("\nEnter Cost Matrix\n");
 
for(i=0;i < n;i++)
{
printf("\nEnter Elements of Row: %d\n",i+1);
 
for( j=0;j < n;j++)
scanf("%d",&arr[i][j]);
 
comp[i]=0;
}
 
printf("\nThe cost list is:");
 
for( i=0;i < n;i++)
{
printf("\n");
 
for(j=0;j < n;j++)
printf("\t%d",arr[i][j]);
}
}
 
void minimum_cost(int city)
{
int i,ncity;
 
comp[city]=1;
 
printf("%d--->",city+1);
ncity=least(city);
 
if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=arr[city][ncity];
 
return;
}
 
minimum_cost(ncity);
}
 
int least(int c)
{
int i,nc=999;
int min=999,kmin;
 
for(i=0;i < n;i++)
{
if((arr[c][i]!=0)&&(comp[i]==0))
if(arr[c][i]+arr[i][c] < min)
{
min=arr[i][0]+arr[c][i];
kmin=arr[c][i];
nc=i;
}
}
 
if(min!=999)
cost+=kmin;
 
return nc;
}
 
int main()
{
    get_input();
     
    printf("\nThe Path is:\n");
    minimum_cost(0); 
     
    printf("\nMinimum cost is %d\n ",cost);
     
return 0;
}