#include<stdio.h>
int matrix[25][25], visited_cities[10], limit, cost = 0;
int tsp(int c)
{
int count, nearest_city = 999;
int minimum = 999, temp;
for(count = 0; count < limit; count++)
{
if((matrix[c][count] != 0) && (visited_cities[count] == 0))
{
if(matrix[c][count] < minimum)
{
minimum = matrix[count][0] + matrix[c][count];
}
temp = matrix[c][count];
nearest_city = count;
}
}
if(minimum != 999)
{
cost = cost + temp;
}
return nearest_city;
}
void minimum_cost(int city)
{
int nearest_city;
visited_cities[city] = 1;
printf("%d ", city + 1);
nearest_city = tsp(city);
if(nearest_city == 999)
{
nearest_city = 0;
printf("%d", nearest_city + 1);
cost = cost + matrix[city][nearest_city];
return;
}
minimum_cost(nearest_city);
}
int main()
{
int i, j;
scanf("%d", &limit);
for(i = 0; i < limit; i++)
{
for(j = 0; j < limit; j++)
{
scanf("%d", &matrix[i][j]);
}
visited_cities[i] = 0;
}
printf("Path: ");
minimum_cost(0);
printf("\nMinimum Cost: \t");
printf("%d\n", cost);
return 0;
}
- Problem Description
Travelling Salesman Problem (TSP) is a touring problem in which n cities and distance between each pair is given. We have to find a shortest route to visit each city exactly once and come back to the starting point.
Input
First line contains an integer N = number of cities
Enter the cost matrix
Output
Output an optimal path and the minimum cost. - Test Case 1
Input (stdin)4
1 5 4 2
2 1 5 4
9 6 2 4
7 5 3 2
Expected OutputPath: 1 4 3 2 1
Minimum Cost: 13 - Test Case 2
Input (stdin)4
1 2 3 4
5 6 7 8
3 4 5 6
9 8 4 3
Expected OutputPath: 1 4 3 2 1
Minimum Cost: 17