Objective

The objective of this project is to demonstrate a solution to the Traveling Salesman Problem (TSP),
which aims to find the shortest possible route that visits a set of cities exactly once and returns to
the original city. This problem is significant in the field of combinatorial optimization and is widely
applicable in logistics, planning, and the manufacturing of circuits.

Code Implementation

#include 
#include 

#define MAX 10

int cost[MAX][MAX], visited[MAX];
int n, min_cost = INT_MAX;

void tsp(int current_city, int count, int cost_so_far) {
    if (count == n && cost_so_far + cost[current_city][0] < min_cost) {
        min_cost = cost_so_far + cost[current_city][0];
        return;
    }

    for (int next_city = 0; next_city < n; next_city++) {
        if (!visited[next_city] && cost[current_city][next_city] != 0) {
            visited[next_city] = 1;
            tsp(next_city, count + 1, cost_so_far + cost[current_city][next_city]);
            visited[next_city] = 0;
        }
    }
}

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

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

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

    visited[0] = 1; // Start from the first city
    tsp(0, 1, 0);

    printf("Minimum cost: %d\n", min_cost);
    return 0;
}
        

Program Structure Explanation

The program is structured as follows:

• Includes: It includes necessary headers such as stdio.h and limits.h for input/output operations and defining integer limits.
• Macros: #define MAX 10 defines the maximum number of cities.
• Global Variables: It declares global variables for cost matrix, visited cities array, number of cities, and the minimum cost found.
• Recursive Function (tsp): This function recursively visits each city, updating the minimum cost whenever all cities have been visited.
• Main Function: This is the entry point of the program where it prompts for the number of cities and the cost matrix, initializes the visited array, and calls the tsp function.

How to Run the Program

1. Make sure you have a C compiler installed (like GCC).
2. Copy the code into a text file and save it with a .c extension (e.g., tsp.c).
3. Open a terminal and navigate to the directory where the file is saved.
4. Compile the program using the command:
   gcc tsp.c -o tsp
5. Run the program with the command:
   ./tsp
6. Input the number of cities and the cost matrix when prompted.