## C Program To Solve Travelling Salesman Problem

Learn How To Implement Travelling Salesman Problem in C Programming Language. The TSP is a Branch and Bound Algorithm that is one of the different **types of algorithms in data structures**. The Travelling Salesman Problem is also famously known as **Travelling Salesperson Problem**.

The Travelling Salesperson Algorithm can be solved using different types of algorithms such as:

- Backtracking Algorithm
- Branch and Bound Algorithm
- Dynamic Programming
**Christofides Algorithm**

**Must Read: C Program To Implement Banker’s Algorithm**

#### What is Travelling Salesman Problem?

The TSP Algorithm is stated as – “From a given set of N cities and distance between each pair of the cities. Find the Minimum Path Length in such a way that it covers each and every city exactly once (without repetition of any path) and terminate the traversal at the starting point or the starting city from where the traversal of the TSP Algorithm was initiated.

So, basically you have to find the **shortest route** to traverse all the cities without repeating any city and finally end your journey from where you started.

Real World Applications of Travelling Salesperson Algorithm

- Logistics
- Planning
- Microchips Manufacturing

**Must Read: C Program For N Queens Problem Implementation**

#### C Program For Travelling Salesman Problem using Array

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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include<stdio.h> int matrix[25][25], visited_cities[10], limit, cost = 0; int tsp(int c) { int count, nearest_city = 999; int minimum = 999, temp; for(count = 0; count < limit; count++) { if((matrix[c][count] != 0) && (visited_cities[count] == 0)) { if(matrix[c][count] < minimum) { minimum = matrix[count][0] + matrix[c][count]; } temp = matrix[c][count]; nearest_city = count; } } if(minimum != 999) { cost = cost + temp; } return nearest_city; } void minimum_cost(int city) { int nearest_city; visited_cities[city] = 1; printf("%d ", city + 1); nearest_city = tsp(city); if(nearest_city == 999) { nearest_city = 0; printf("%d", nearest_city + 1); cost = cost + matrix[city][nearest_city]; return; } minimum_cost(nearest_city); } int main() { int i, j; printf("Enter Total Number of Cities:\t"); scanf("%d", &limit); printf("\nEnter Cost Matrix\n"); for(i = 0; i < limit; i++) { printf("\nEnter %d Elements in Row[%d]\n", limit, i + 1); for(j = 0; j < limit; j++) { scanf("%d", &matrix[i][j]); } visited_cities[i] = 0; } printf("\nEntered Cost Matrix\n"); for(i = 0; i < limit; i++) { printf("\n"); for(j = 0; j < limit; j++) { printf("%d ", matrix[i][j]); } } printf("\n\nPath:\t"); minimum_cost(0); printf("\n\nMinimum Cost: \t"); printf("%d\n", cost); return 0; } |

**Must Read: C Program To Implement Producer Consumer Problem Algorithm**

#### Output

In case you get any Compilation Errors or any doubts in this Travelling Salesman Problem C Program, let us know about it in the Comment Section below. Find more information about Travelling Salesman Algorithm on **Wikipedia**.

This is really good explanation. Great compilation of travelling salesman algorithm, code and explanation.

I found this concept so interesting.This is really fascinating that we can solve our routine life travelling problems with this tsp algorithm. Thank you so much.

Thanks for the tsp c program. This is a very famous interview question.

Is this similar to Minimum Spanning Tree, Djikstra, Kruskal and Prims Algorithm?

Yes. I think so. All these algorithms find the minimum cost to travel from one location to another.

The TSP Problem is one of the best examples for NP Problems. This problem can be solved in Non Deterministic Polynomial Time.

What is Dynamic Programming actually? Why is it used for this TSP in C Programming?

The travelling salesman algorithm is a NP Problem.

The travelling salesperson problem can be effeciently solved using Branch and Bound algorithm too. In fact, this method is an effective approach towards solving the TSP problem in short time by pruning the unnecessary branches.

temp =matrix[][];

nearest_city=count;

will come under the if(a[][]<m) domain that's how it will give minimum cost otherwise everytime it will give 14321 path irrespective of the input,

i mean that bracket at line number 16 will come at line number 19

thanks for the code it helped me a lot 🙂

in TSP we have to enter Infinity value to the Route like A->A how can i implement this to it…. if possible czn u explain this code

please Explain Approach!! 🙂