Perform Travelling Salesman Problem
Here, you will know source code to perform Travelling salesman problem in C language.
Define traveling salesman problem
The Traveling Salesman Problem (TSP) is a problem in Computer Science, where you need to find the shortest possible route that visits a list of cities exactly once and returns to the starting city. It’s used in logistics and optimization, and finding the best solution can be very hard for large datasets.
C program to perform Travelling Salesman Problem
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | //Implement travelling salesman problem in c language #include <stdio.h> #include <stdlib.h> #define MAX 20 int num; int cost[MAX][MAX]; int visited[MAX]; int min_cost; int tour[MAX+1]; void tsp(int pos, int c) { int i, nc; if(pos == num) { if(cost[tour[pos-1]][tour[0]] != 0 && c+cost[tour[pos-1]][tour[0]] < min_cost) { min_cost = c+cost[tour[pos-1]][tour[0]]; for(i=0; i<num; i++) printf("%d ", tour[i]); printf("%d", tour[0]); printf("\nMinimum Cost: %d\n", min_cost); } return; } for(i=0; i<num; i++) { if(cost[tour[pos-1]][i] != 0 && !visited[i]) { nc = c + cost[tour[pos-1]][i]; if(nc < min_cost) { tour[pos] = i; visited[i] = 1; tsp(pos+1, nc); visited[i] = 0; } } } } int main() { int i, j; printf("Enter number of cities: "); scanf("%d", &num); printf("Enter cost of matrix: \n"); for(i=0; i<num; i++) for(j=0; j<num; j++) scanf("%d", &cost[i][j]); for(i=0; i<num; i++) visited[i] = 0; tour[0] = 0; min_cost = 900; tsp(1, 0); return 0; } |
Output
Enter number of cities: 5
Enter cost of matrix:
23 45 67 56 89
23 45 16 87 56
34 65 47 87 90
12 34 32 56 73
53 12 50 30 25
0 0 1 2 3 0
Minimum Cost: 183
0 0 1 4 3 0
Minimum Cost: 166
0 0 3 1 2 0
Minimum Cost: 163
Read Also
Find Minimum Spanning Tree using Kruskal’s Algorithm
Implement N Queens Problem using Backtracking
Knapsack Problem Using Dynamic Programming in C