C Program To Solve Travelling Salesman Problem

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.”

C Program To Solve Travelling Salesman Algorithm in C Programming using Branch and Bound

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:

Backtracking Algorithm
Branch and Bound Algorithm
Dynamic Programming
Christofides Algorithm

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

#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

Travelling Salesman Problem in C Programming using Arrays

Disadvantages

This might lead to an incomplete Hamiltonian cycle.
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.

Smart Tip: Worried about your incomplete software project? Get an easy remote access to all your programming/testing tools on your smartphone device(android/iOS) with powerful virtual desktop from CloudDesktopOnline.com powered by one of the best DaaS provider – www.Apps4Rent.com.

19 thoughts on “Travelling Salesman Problem C Program”

Pankaj Kapoor September 12, 2016

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