Traveling Salesman Problem

#include <stdio.h>
#include <limits.h>

#define MAX 10
int n;
int graph[MAX][MAX];
int visited[MAX];

// Function to find minimum cost using backtracking
int tsp(int city, int count, int cost) {
    if (count == n && graph[city][0] > 0)  // All cities visited, return to start
        return cost + graph[city][0];

    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && graph[city][i] > 0) {
            visited[i] = 1;
            int temp = tsp(i, count + 1, cost + graph[city][i]);
            ans = (temp < ans) ? temp : ans;
            visited[i] = 0;
        }
    }
    return ans;
}

int main() {
    printf("Enter number of cities: ");
    scanf("%d", &n);

    printf("Enter cost matrix (0 if no path):\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    for (int i = 0; i < n; i++)
        visited[i] = 0;

    visited[0] = 1;  // Start from city 0
    int minCost = tsp(0, 1, 0);

    printf("Minimum cost to visit all cities: %d\n", minCost);

    return 0;
}