Question Name:Travelling Sales Man

#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

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.