Travelling Salesperson Problem

#include<stdio.h>

#include<conio.h>

#define max 10

#define INFINITY 1000

int w[max][max];

intn_size;

int p[max];

ints_size;

int stack[max];

int route[max];

int min;

voidin_dat()

{

printf("\n Enter the number of nodes : ");

scanf("%d",&n_size);

fflush(stdin);

int i;

for(i=0;i<n_size;i++)

 {

w[i][i] = 0;

for(int j=i+1;j<n_size;j++)

  {

printf("\n\n Enter the weight of edge '%c' and '%c': ",65+i,65+j);

scanf("%d",&w[i][j]);

w[j][i] = w[i][j];

  }

 }

}

voiddis_dat()

{

printf("\n The Path adjacent matrix \n");

printf("\n ");

for(int i=0;i<n_size;i++)

 {

printf("\n");

for(int j=0;j<n_size;j++)

  {

printf("\t %d",w[i][j]);

  }

 }

getch();

fflush(stdin);

}

voidfindshort(intsr,intct,intss)

{

if(ct == 0)

  {

inttdst=0;    

 //  printf("\n Checking ss= %d sr='%c' :",ss,65+sr);   

   // for(int j=0;j<ss;j++)    

   //   {

    //    printf(" %c",65+stack[j]);   

     // }

for(int k=0;k<ss-1;k++)

    {

tdst += w[stack[k]][stack[k+1]];

     //printf(" p[%c]=%c",65+stack[k],65+stack[k+1]);

    }

if(min >tdst)

    {

min = tdst;

for(int l=0;l<ss+n_size-1;l++)

      {

route[l] = stack[l];

       //printf(" p[%c]=%c",65+stack[k],65+stack[k+1]);

      }

    }

  }

else

  { 

  //int ret = -1;

  //int min = INFINITY;

  //inttdst;

for(int i=0;i<n_size;i++)

  {

intind = 0;                    

if(w[sr][i] != 0)

    {

    //  printf("\n Checking ss= %d sr='%c' i='%c' :",ss,65+sr,65+i);         

for(int j=0;j<ss;j++)    

      {

      //  printf(" %c",65+stack[j]);   

if(stack[j] == i)

        {

ind = -1;         

        }    

      } 

     // printf(" (%d)",min); 

if(ind != -1)

      {

      // printf(" .. VALID .. ");     

stack[ss] = i;     

       //ret = 0;    

       //printf(" w[%c][%c] = %d",65+sr,65+i,w[sr][i]);    

findshort(i,ct-1,ss+1);      

       } 

      }

    }

  } 

}

void MSG()

{

chars,d;

intsi,di;   

printf("\nEnter the source node : ");

scanf("%c",&s);

fflush(stdin);

si = (int) s-65;

stack[0] = si;

s_size = 1;

min = INFINITY;

findshort(si,n_size-1,1);

printf("\n The shortest distance from '%c' : %d",s,min);

getch();

printf("\n The shortest path : ");

for(int k=0;k<n_size;k++)

  {

printf(" %c",65+route[k]);

  }

getch();

}

int main()

{

// clrscr();

in_dat();

dis_dat();

MSG();

return 0;

}