#include<stdio.h>
int a[10][10],visited[10],n,cost=0;
int tsp(int c)
{
int cnt, near_city = 999;
int min = 999, temp;
for(cnt = 0; cnt < n; cnt++)
{
if((a[c][cnt] != 0) && (visited[cnt] == 0))
{
if(a[c][cnt] < min)
{
min = a[cnt][0] + a[c][cnt];
}
temp = a[c][cnt];
near_city = cnt;
}
}
if(min!= 999)
{
cost = cost + temp;
}
return near_city;
}
void min_cost(int city)
{
int near_city;
visited[city] = 1;
printf(“%d “, city + 1);
near_city = tsp(city);
if(near_city == 999)
{
near_city = 0;
printf(“%d”, near_city + 1);
cost = cost + a[city][near_city];
return;
}
min_cost(near_city);
}
void get()
{
int i, j;
printf(“Enter Total Number of Cities:\t”);
scanf(“%d”, &n);
printf(“\nEnter Cost Matrix\n”);
for(i = 0; i < n; i++)
{
printf(“\nEnter %d Elements in Row[%d]\n”,n, i + 1);
for(j = 0; j < n; j++)
{
scanf(“%d”, &a[i][j]);
}
visited[i] = 0;
}
printf(“\nEntered Cost Matrix\n”);
for(i = 0; i < n; i++)
{
printf(“\n”);
for(j = 0; j < n; j++)
{
printf(“%d “, a[i][j]);
}
}
}
/*
================================== OUTPUT ======================================
int main()
{
get();
printf(“\n\n the path is:\n\n”);
min_cost(0);
printf(“\n\nMinimum Cost: \t”);
printf(“%d\n”, cost);
return 0;
}
student@sdl17:~$ gcc tsp.c
student@sdl17:~$ ./a.out
Enter Total Number of Cities: 5
Enter Cost Matrix
Enter 5 Elements in Row[1]
1 2 2 5 3
Enter 5 Elements in Row[2]
1 2 4 5 6
Enter 5 Elements in Row[3]
1 2 4 5 6
Enter 5 Elements in Row[4]
1 2 5 4 8
Enter 5 Elements in Row[5]
7 4 3 2 5
Entered Cost Matrix
1 2 2 5 3
1 2 4 5 6
1 2 4 5 6
1 2 5 4 8
7 4 3 2 5
the path is:
1 5 4 3 2 1
Minimum Cost: 13
student@sdl17:~$
*/
Pocket Study Blog 