Travelling Salesman Problem using backtracking


using c program through data structures

* Travelling Salesman Problem using backtracking*/
#include"stdio.h"
int x[15],used[15];
int adj[15][15]={0};
int path[15][15],wght[15];
int c,min;
int path_ok(int k,int n)
{
if(used[x[k]])
return 0;
if(k‹n-1)
return(adj[x[k-1]][x[k]]);
else
return(adj[x[k-1]][x[k]] && adj[x[k]][x[0]]);
}
void TSP(int k,int n)
{
int i,sum;
for(x[k]=1;x[k]{
if(path_ok(k,n))
{
used[x[k]]=1;
if(k==n-1)
{
sum=0;
printf("\n\n\tPOSSIBLE PATH %d : ",c+1);
for(i=0;i{
printf("%d\t",x[i]);
path[c][i]=x[i];
sum+=adj[x[i]][x[i+1]];
}
printf(" : %d",sum);
wght[c]=sum;
if(c==0 || summin=sum;
c++;
used[x[k]]=0;
getch();
}
else
TSP(k+1,n);
used[x[k]]=0;
}
}
}
void findmin(int n)
{
int i,j;
for(i=0;iif(wght[i]==min)
{
printf("\n\n\tMINIMUM PATH : ");
for(j=0;jprintf("%d\t",path[i][j]);
}
}
void main()
{
int i,n,j;
int edg;
clrscr();
printf("\n\n\t\tTRAVELLING SALESMAN PROBLEM\n\n");
printf("\n\tEnter the no. of Cities : ");
scanf("%d",&n);
printf("\n\n Enter the Cost if path Exist Between cities.:{c1,c2}.Else Enter 0\n\n");
printf("\n\tCITIES\t\tCOST\n\n");
for(i=0;ifor(j=i+1;j{
printf("\n\t %d------ %d \t:",i,j);
scanf("%d",&edg);
if(edg)
adj[i][j]=adj[j][i]=edg;
}
used[0]=1;
TSP(1,n);
if(!c)
printf("\n\n\t\tNO PATH FOUND TO COVER ALL THE CITIES\n\n");
else
{
printf("\n\n\t\tMINIMUM COST IS %d AND THE PATHS ARE \n\n",min);
findmin(n);
}
getch();
}


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: