2. Write a program to perform travelling salesman problem. || DAA

 #include <stdio.h> 

#include <limits.h> 

#define MAX_CITIES 10 

void swap(int *a, int *b) { 

int temp = *a; 

*a = *b; 

*b = temp; 

} 

void nearestNeighbor(int cities[], int numCities, int *minCost) { 

int visited[MAX_CITIES] = {0}; // Mark cities as unvisited 

*minCost = 0; 

for (int i = 0; i < numCities - 1; i++) { 

int minDistance = INT_MAX; 

int nearestCity = -1; 

for (int j = 0; j < numCities; j++) { 

if (!visited[j] && cities[i * numCities + j] < minDistance) { 

minDistance = cities[i * numCities + j]; 

nearestCity = j; 

} 

} 

visited[nearestCity] = 1; 

*minCost += minDistance; 

} 

// Add the distance back to the starting city to complete the tour 

*minCost += cities[(numCities - 1) * numCities]; 

} 

int main() { 

int numCities, i, j; 

printf("Enter the number of cities (max %d): ", MAX_CITIES); 

scanf("%d", &numCities); 

if (numCities <= 0 || numCities > MAX_CITIES) { 

printf("Invalid number of cities.\n"); 

return 1; 

} 

int cities[MAX_CITIES][MAX_CITIES]; 

printf("Enter the distances between cities:\n"); 

for (i = 0; i < numCities; i++) { 

for (j = 0; j < numCities; j++) { 

printf("Distance from city %d to city %d: ", i + 1, j + 1); 

scanf("%d", &cities[i][j]); 

} 

} 

int minCost; 

nearestNeighbor((int *)cities, numCities, &minCost); 

printf("\nMinimum Cost: %d\n", minCost); 

return 0; 

}