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.

Powered By
CHP Adblock Detector Plugin | Codehelppro