7. Write a C program to demonstrate Travelling Salesman Problem.
// Algorithm: TravelingSalesmanProblem
// Input: num_cities: Number of cities to visit, distance[MAX_CITIES][MAX_CITIES]: Distance
matrix where distance[i][j] represents the distance from city i to city j (0 if no direct
path)
// Output: min_cost: Minimum cost of the tour that visits all cities exactly once and returns
to start
Step 1: Initialize global variables:
num_cities ← user input
distance[][] ← user input matrix
path[MAX_CITIES] ← empty array to store current path
min_cost ← INT_MAX (maximum integer value)
Step 2: Set starting point:
path[0] ← 0 (start with first city)
visited_mask ← 1 << 0 (mark first city as visited)
Step 3: Call find_min_path(1, 0, visited_mask)
// Recursive function to find minimum cost path
Function find_min_path(current_pos, cost_so_far, visited_mask):
Step 4: If all cities visited (visited_mask == (1 << num_cities) - 1):
If return path to start exists:
total_cost ← cost_so_far + distance[path[current_pos-1]][path[0]]

If total_cost < min_cost:
min_cost ← total_cost

Return
Step 5: For next_city ← 0 to num_cities-1:
If next_city not visited (!(visited_mask & (1 << next_city))):
If path exists from current city to next_city:

path[current_pos] ← next_city
Recursively call find_min_path:

current_pos+1,

cost_so_far + distance[path[current_pos-1]][next_city],

visited_mask | (1 << next_city)

Step 6: After recursion completes:
If min_cost != INT_MAX:

Print "Minimum cost: " + min_cost

Else:
Print "No valid route exists"
#include< stdio.h>
#include< limits.h>
#define MAX_CITIES 10
int num_cities;
int distance[MAX_CITIES][MAX_CITIES];
int path[MAX_CITIES];
int min_cost = INT_MAX;
void find_min_path(int current_pos, int cost_so_far, int visited_mask)

{
int next_city;
if(visited_mask == (1 << num_cities) - 1)
{
if(distance[path[current_pos-1]][path[0]] > 0)

{

int total_cost = cost_so_far + distance[path[current_pos-1]][path[0]];
if(total_cost < min_cost) min_cost = total_cost;
}
return;
}
for(next_city = 0; next_city < num_cities; next_city++)
if(!(visited_mask & (1 << next_city)))

{

if(distance[path[current_pos-1]][next_city] > 0)

{

path[current_pos] = next_city;
find_min_path(current_pos+1,
cost_so_far + distance[path[current_pos-1]][next_city],

visited_mask | (1 << next_city));

}
}
}
void main()
{
int i, j;
printf("Enter number of cities: ");
scanf("%d", &num_cities);
printf("Enter distance matrix (0 for no direct path):\n");
for(i = 0; i < num_cities; i++)
for(j = 0; j < num_cities; j++)
scanf("%d", &distance[i][j]);
path[0] = 0;
find_min_path(1, 0, 1 << 0);
if(min_cost != INT_MAX)
printf("Minimum cost: %d\n", min_cost);
else
printf("No valid route exists\n");
}