# Travelling Salesman Problem C Program

By | September 12, 2016

Let us learn how to implement and solve travelling salesman problem in C programming with its explanation, output, disadvantages and much more.

#### What is Travelling Salesman Problem?

The travelling salesman problem follows the approach of the branch and bound algorithm that is one of the different types of algorithms in data structures.

This algorithm falls under the NP-Complete problem. It is also popularly known as Travelling Salesperson Problem.

#### Problem Statement

The TSP algorithm states that – “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.

In other words, the travelling salesman problem enables to find the Hamiltonian cycle of minimum weight. A Hamiltonian cycle is a route that contains every node only once.

Alternatively, the travelling salesperson algorithm can be solved using different types of algorithms such as:

#### Real World Applications of Travelling Salesperson Algorithm

• Logistics
• Planning
• Microchips Manufacturing

Must Read: C Program For N Queens Problem Implementation

Note: This code for travelling salesman algorithm in C programming using branch and bound algorithm is compiled with GNU GCC compiler using gEdit and Terminal on Linux Ubuntu operating system.

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

Must Read: C Program To Implement Producer Consumer Problem Algorithm

#### Output

1. This might lead to an incomplete Hamiltonian cycle.
2. The TSP algorithm selects the best optimum route available at a particular instance without thinking of the future routes. This could lead to a problem.

If you have any doubts about Travelling Salesman Problem C Program, let us know about it in the comment section. Find more about it on Wikipedia.

## 19 thoughts on “Travelling Salesman Problem C Program”

1. Pankaj Kapoor

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

2. Vikas Khurana

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.

3. Sugan Reddy

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

4. Omkar Chavan

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

5. Vishal Upadhyay

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

6. Ujjwal Kumar

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

7. Jagdish Kashyap

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

8. Vikramank Kadam

The travelling salesman algorithm is a NP Problem.

9. Sachin Bhoi

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.

10. Tushar jumani

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

1. Tushar jumani

thanks for the code it helped me a lot 🙂

11. Ajay N

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

12. Anonymous

13. Jenifer Longoria

Muchas gracias..

14. Ben Thurston

I assumed that the cost matrix would be the difference between two cities defined by the entry; that is, row 1 column 3 would be the cost to travel from 1 to 3. But if this is the case, then [3,1] should be equal to [1,3] and it isn’t. So can someone tell me how the cost matrix should be structured? Also, does Tushar Jumani’s comment on 4/2 mean that there’s an error in the code, that should be corrected?

15. Ben Thurston

I have to say I’m very skeptical of this algorithm. I ran it for 10 cities, with random distances (costs) between cities. The result was 1 10 9 8 7 6 5 4 3 2 1. This is an identical pattern to the 4 city test run. Tushar Jumani’s comment that some condition (that I don’t begin to understand) gives the same path “irrespective of the input” seems to be accurate. I’d love for someone to post a correction.

16. ravi

please explain the functions in the program

17. Nooruddin

For any input the above code gives same path traversed

18. dguai

this is not dynamic programming.