Resources » Articles/Knowledge Sharing » Education

Travelling Salesman Problem using backtracking


Last Updated:   Category: Education    
Author: Member Level: Silver    Points: 2


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();
}


Did you like this resource? Share it with your friends and show your love!




Responses to "Travelling Salesman Problem using backtracking"

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

Feedbacks      

Post 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:   Sign In to fill automatically.
    Email: (Will not be published, but required to validate comment)



    Type the numbers and letters shown on the left.


    Submit Article     Return to Article Index

    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

    ISC Technologies, Kochi - India. Copyright © All Rights Reserved.