Travelling Salesman Problem (TSP) Algorithm Implementation

Before we start learning the implementation of Travelling Salesman Problem in c, We need to understand the problem and its solution.

Travelling Salesman Problem algorithm description: There will be a set of cities given along with the distance between each of them. Here, the problem is to find out shortest route by visiting each city exactly once and return back to the starting city.

Understand the Travelling Salesman Problem algorithm :

Consider below given Travelling Salesman Problem example to understand it step by step. Lets say there are four cities {A,B,C,D}. Let assume that each city is connected with every other city.

Here, the challenge is for a salesman to visit each city exactly once starting from city "A". we have assumed that salesman lives in the city "A" and will start travelling from city "A". After visiting all cities salesman will return back to the city "A".

There can be many possible optimal solutions. It is very hard to find an optimal solution for travelling salesman problem, because of that it is also known as NP-complete.

Brute force takes more time to compute the cost to solve TSP. Which means, we have to try all possible permutation combination. Then only we can find the route with the minimum cost. The time complexity for Brute force is O(!n) time, which is very slow.

To reduce this time complexity Dynamic Programming approach is used. Which solves travelling salesman problem in O(n^{^2}2^{^n)} time. Brute force is good for the small graph with a fewer number of nodes, but the dynamic programming approach is better when you have a larger graph.

Understand Travelling Salesman Problem Using Dynamic Programming

To understand the travelling salesman problem more effectively, consider the travelling salesman problem graph shown in the above image. Below is the matrix of the same graph example.

Travelling Salesman Problem matrix example

Consider "A" as a starting node. Next, compute and store the optimal value from A to each node {B, C, D}. Total (n-1)! possible ways to find the shortest route.

1. Consider city A as a starting and ending point.
2. Generate (n-1)! permutation for all cities (nodes)
3. Calculate the cost of every permutation and keep track of the minimum cost permutation
4. Return the permutation with minimum cost

Below mentioned is the dynamic equation for travelling salesman problem to find the shortest route.
 

g(i , S) = min{ C_ik + g(k, S - {k}) }

To understand the above equation, we first need to understand each component of it. S is a subset of cities S ∈ {A, B, C, D}. g(i, S) represents the shortest path after visiting each node exactly once, staring from nodes A to D.

Let's understand it using a given graph and matrix step by step using an easy buy long method.

Travelling Salesman Problem (TSP) using dynamic programming

A -> B -> C -> D -> A
g(i , S) = min{ Cik + g(k, S - {k}) } = CAB + g(B, {C, D}) = CAB + CBC + g(C, {D}) = CAB + CBC + CCD + g(D, ∅) = CAB + CBC + CCD + CDA = 4 + 2 + 5 + 3 = 14

A -> B -> D -> C
g(i , S) = min{ Cik + g(k, S - {k}) } = CAB + g(B, {D, C}) = CAB + CBD + g(D, {C}) = CAB + CBD + CDC + g(C, ∅) = CAB + CBD + CDC + CCA = 4 + 1 + 5 + 1 = 11

A -> C -> B -> D
g(i , S) = min{ Cik + g(k, S - {k}) } = CAC + g(C, {B, D}) = CAC + CCB + g(B, {D}) = CAC + CCB + CBD + g(D, ∅) = CAC + CCB + CBD + CDA = 1 + 2 + 1 + 3 = 7

A -> C -> D -> B
g(i , S) = min{ Cik + g(k, S - {k}) } = CAC + g(C, {D, B}) = CAC + CCD + g(D, {B}) = CAC + CCD + CDB + g(B, ∅) = CAC + CCD + CDB + CBA = 1 + 5 + 1 + 4 = 11

A -> D -> B -> C
g(i , S) = min{ Cik + g(k, S - {k}) } = CAD + g(D, {B, C}) = CAD + CDB + g(B, {C}) = CAD + CDB + CBC + g(C, ∅) = CAD + CDB + CBC + CCA = 3 + 1 + 2 + 1 = 7

A -> D -> C -> B
g(i , S) = min{ Cik + g(k, S - {k}) } = CAD + g(D, {C, B}) = CAD + CDC + g(C, {B}) = CAD + CDC + CCB + g(B, ∅) = CAD + CDC + CCB + CBA = 3 + 5 + 2 + 4 = 14

Here, minimum travelling distance is 7, which includes path A -> C -> B -> D -> A and A -> D -> B -> C -> A.

Program for Travelling Salesman Problem in C with output

#include<stdio.h>

int ary[10][10],completed[10],n,cost=0;

void takeMatrixInput()
{
int i,j;

printf("Enter the number of villages: ");
scanf("%d",&n);

printf("\nEnter the Cost Matrix\n");

for(i=0;i < n;i++)
{
printf("\nEnter Elements of Row: %d\n",i+1);

for( j=0;j < n;j++)
scanf("%d",&ary[i][j]);

visited[i]=0;
}

printf("\n\nThe cost list is:");

for( i=0;i < n;i++)
{
printf("\n");

for(j=0;j < n;j++)
printf("\t%d",ary[i][j]);
}
}

void treeCost(int city)
{
int i,ncity;
if(city!=-1)
{
  visited[city]=1;

  printf("%d--->",city+1);
  ncity=least(city);

  treeCost(ncity);
}
else
{
  printf("%d",1);
}
}

int least(int c)
{
int i,j=0;
int nc = -1;
int kmin = 0;
int isAllVisited = 1;
for(i=0;i < n;i++)
{
if(visited[i]==0)
{
isAllVisited=0;
}
}

for(j=0;j < n;j++)
{
if(isAllVisited == 1)
{
kmin = ary[c][0];
nc=-1;
}
else
{
if((ary[c][j]!=0)&&(visited[j]==0))
{
if(kmin==0)
{
kmin = ary[c][j];
nc =j;
}
else
{
if(ary[c][j] < kmin)
{
kmin = ary[c][j];
nc =j;
}
}
}
}
}
cost+=kmin;

return nc;
}

int main()
{
takeMatrixInput();

printf("\n\nThe Path is:\n");
treeCost(0); //passing 0 because starting vertex

printf("\n\nMinimum cost is %d\n ",cost);

getch();
clrscr();
}

Output:

Enter the number of villages/cities: 4

Enter the Cost Matrix

Enter Elements of Row: 1
0 4 1 3

Enter Elements of Row: 1
4 0 2 1

Enter Elements of Row: 1
1 2 0 5

Enter Elements of Row: 1
3 1 5 0

The cost list is:
0  4  1  3
4  0  2  1
1  2  0  5
3  1  5  0

The path is:
1--->3--->2--->4--->1

Minimum cost is 7

Travelling Salesman Problem (TSP) c program output

Program explanation :
To find the shortest path using Travelling Salesman Problem in c, Here we have defined 3 functions. Each 3 has a different responsibility.

Function takeMatrixInput() is responsible to take input from a user to give the size of the matrix. Based on the size of the matrix take row elements to store in array ary[i][j]. After that array ary[i][j] is printed using for loop.

Then function treeCost(int city) is initialized with 0, which defines starting vertex 0. After that visited[city] array is set to 1 to keep track of visited cities and then least(int c) is called.

Function least(int c) finds the next nearest node and calculates the cost recursively using for loop. And at last program prints shortest path and cost.

Note: The program is written considering the representation of nodes  A to Z with 1 to an X integer value.