Resources » Education

# Travelling Salesman Problem using backtracking

 Updated: 08-Aug-2010 Category: Education Author: kalyan 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
Complete the action items below to enter to win an iPad Mini from India Study Channel!

### Subscribe to Email

• Get Jobs by Email
• Forum posts by Email
• Articles by Email
• Awards & Gifts
Active Members
TodayLast 7 Days
more...

### Online Members

M. K.
More...

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

 Click the "Follow" button above to follow Tony John