Travelling salesman problem

/*
* Source: www.pracspedia.com
*
* Status: Tested OK
* Title: Traveling salesman problem
* Name: Akshay Thakare
*/

#include<stdio.h>
int a[10][10],visited[10],n,cost=0;

void get()
{
int i,j;
printf("Enter No. of Cities: ");
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",&a[i][j]);
visited[i]=0;
}
}

void mincost(int city)
{
int i,ncity;
visited[city]=1;
printf("%d -->",city+1);
ncity=least(city);
if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=a[city][ncity];
return;
}
mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i < n;i++)
{
if((a[c][i]!=0)&&(visited[i]==0))
if(a[c][i] < min)
{
min=a[i][0]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}

void put()
{
printf("\n\nMinimum cost:");
printf("%d",cost);
}

void main()
{
get();
printf("\n\nThe Path is:\n\n");
mincost(0);
put();
}

/*

OUTPUT:
Enter No. of Cities: 4
Enter Cost Matrix
Enter Elements of Row # : 1
1
5
4
2
Enter Elements of Row # : 2
2
1
5
4
Enter Elements of Row # : 3
9
6
2
4
Enter Elements of Row # : 4
7
5
3
4
The cost list is:
1 5 4 2

2 1 5 4

9 6 2 4

7 5 3 4

The Path is:

1 –->4 -–>3 -–>2 -–>1
*/
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s