Here you will learn about Travelling Salesman Problem (TSP) with example and also get a program that implements Travelling Salesman Problem in C and C++.

Let say there are some villages (1, 2, 3, 4, 5). To work with worst case let assume each villages connected with every other villages. And there is a Salesman living in village 1 and he has to sell his things in all villages by travelling and he has to come back to own village 1.

He has to travel each village exactly once, because it is waste of time and energy that revisiting same village. This is same as visiting each node exactly once, which is **Hamiltonian Circuit**. But our problem is bigger than Hamiltonian cycle because this is not only just finding Hamiltonian path, but also we have to find shortest path.

Finally the problem is we have to visit each vertex exactly once with minimum edge cost in a graph.

Brute Force Approach takes O (n^{n}) time, because we have to check (n-1)! paths (i.e all permutations) and have to find minimum among them.

The correct approach for this problem is solving using Dynamic Programming.

Dynamic Programming can be applied only if main problem can be divided into sub-problems. Let’s check that.

## Travelling Salesman Problem (TSP) Using Dynamic Programming

### Example Problem

Above we can see a complete directed graph and cost matrix which includes distance between each village. We can observe that cost matrix is symmetric that means distance between village 2 to 3 is same as distance between village 3 to 2.

Here problem is travelling salesman wants to find out his tour with minimum cost.

Say it is T (1,{2,3,4}), means, initially he is at village 1 and then he can go to any of {2,3,4}. From there to reach non-visited vertices (villages) becomes a new problem. Here we can observe that main problem spitted into sub-problem, this is property of dynamic programming.

**Note:** While calculating below right side values calculated in bottom-up manner. Red color values taken from below calculations.

T ( 1, {2,3,4} ) = minimum of

= { (1,2) + T (2, {3,4} ) 4+**6**=10

= { (1,3) + T (3, {2,4} ) 1+**3**=4

= { (1,4) + T (4, {2,3} ) 3+**3**=6

Here minimum of above 3 paths is answer but we know only values of (1,2) , (1,3) , (1,4) remaining thing which is T ( 2, {3,4} ) …are new problems now. First we have to solve those and substitute here.

T (2, {3,4} ) = minimum of

= { (2,3) + T (3, {4} ) 2+**5**=7

= { (2,4) + T {4, {3} ) 1+**5**=6

T (3, {2,4} ) = minimum of

= { (3,2) + T (2, {4} ) 2+**1**=3

= { (3,4) + T {4, {2} ) 5+**1**=6

T (4, {2,3} ) = minimum of

= { (4,2) + T (2, {3} ) 1+**2**=3

= { (4,3) + T {3, {2} ) 5+**2**=7

T ( 3, {4} ) = (3,4) + T (4, {} ) 5+0=5

T ( 4, {3} ) = (4,3) + T (3, {} ) 5+0=5

T ( 2, {4} ) = (2,4) + T (4, {} ) 1+0=1

T ( 4, {2} ) = (4,2) + T (2, {} ) 1+0 = 1

T ( 2, {3} ) = (2,3) + T (3, {} ) 2+0 = 2

T ( 3, {2} ) = (3,2) + T (2, {} ) 2+0=2

Here T ( 4, {} ) is reaching base condition in recursion, which returns 0 (zero ) distance.

This is where we can find final answer,

T ( 1, {2,3,4} ) = minimum of

= { (1,2) + T (2, {3,4} ) 4+**6**=10 in this path we have to add +1 because this path ends with 3. From there we have to reach 1 so 3->1 distance 1 will be added total distance is 10+1=11

= { (1,3) + T (3, {2,4} ) 1+**3**=4 in this path we have to add +3 because this path ends with 3. From there we have to reach 1 so 4->1 distance 3 will be added total distance is 4+3=7

= { (1,4) + T (4, {2,3} ) 3+**3**=6 in this path we have to add +1 because this path ends with 3. From there we have to reach 1 so 3->1 distance 1 will be added total distance is 6+1=7

Minimum distance is **7** which includes path **1->3->2->4->1.**

After solving example problem we can easily write recursive equation.

### Recursive Equation

T (i , s) = min ( ( i , j) + T ( j , S – { j }) ) ; S!= Ø ; j € S ;

S is set that contains non visited vertices

= ( i, 1 ) ; S=Ø, This is base condition for this recursive equation.

Here,

T (i, S) means We are travelling from a vertex “i” and have to visit set of non-visited vertices “S” and have to go back to vertex 1 (let we started from vertex 1).

( i, j ) means cost of path from node i to node j

If we observe the first recursive equation from a node we are finding cost to all other nodes (i,j) and from that node to remaining using recursion ( T (j , {S-j}))

But it is not guarantee that every vertex is connected to other vertex then we take that cost as infinity. After that we are taking minimum among all so the path which is not connected get infinity in calculation and won’t be consider.

If S is empty that means we visited all nodes, we take distance from that last visited node to node 1 (first node). Because after visiting all he has to go back to initial node.

### Time Complexity

Since we are solving this using Dynamic Programming, we know that Dynamic Programming approach contains sub-problems.

Here after reaching i^{th} node finding remaining minimum distance to that i^{th} node is a sub-problem.

If we solve recursive equation we will get total **(n-1) 2 ^{(n-2) }**sub-problems, which is

**O (n2**.

^{n})Each sub-problem will take ** O (n)** time (finding path to remaining **(n-1)** nodes).

Therefore total time complexity is **O (n2 ^{n}) * O (n) = O (n^{2}2^{n})**

Space complexity is also number of sub-problems which is **O (n2 ^{n})**

### Program for Travelling Salesman Problem in C

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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<stdio.h> int ary[10][10],completed[10],n,cost=0; void takeInput() { 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]); completed[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 mincost(int city) { int i,ncity; completed[city]=1; printf("%d--->",city+1); ncity=least(city); if(ncity==999) { ncity=0; printf("%d",ncity+1); cost+=ary[city][ncity]; return; } mincost(ncity); } int least(int c) { int i,nc=999; int min=999,kmin; for(i=0;i < n;i++) { if((ary[c][i]!=0)&&(completed[i]==0)) if(ary[c][i]+ary[i][c] < min) { min=ary[i][0]+ary[c][i]; kmin=ary[c][i]; nc=i; } } if(min!=999) cost+=kmin; return nc; } int main() { takeInput(); printf("\n\nThe Path is:\n"); mincost(0); //passing 0 because starting vertex printf("\n\nMinimum cost is %d\n ",cost); return 0; } |

**Output**

*Enter the number of villages: 4*

*Enter the Cost Matrix*

*Enter Elements of Row: 1*

*0 4 1 3*

*Enter Elements of Row: 2*

*4 0 2 1*

*Enter Elements of Row: 3*

*1 2 0 5*

*Enter Elements of Row: 4*

*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*

### Program for Travelling Salesman Problem in C++

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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include<iostream> using namespace std; int ary[10][10],completed[10],n,cost=0; void takeInput() { int i,j; cout<<"Enter the number of villages: "; cin>>n; cout<<"\nEnter the Cost Matrix\n"; for(i=0;i < n;i++) { cout<<"\nEnter Elements of Row: "<<i+1<<"\n"; for( j=0;j < n;j++) cin>>ary[i][j]; completed[i]=0; } cout<<"\n\nThe cost list is:"; for( i=0;i < n;i++) { cout<<"\n"; for(j=0;j < n;j++) cout<<"\t"<<ary[i][j]; } } int least(int c) { int i,nc=999; int min=999,kmin; for(i=0;i < n;i++) { if((ary[c][i]!=0)&&(completed[i]==0)) if(ary[c][i]+ary[i][c] < min) { min=ary[i][0]+ary[c][i]; kmin=ary[c][i]; nc=i; } } if(min!=999) cost+=kmin; return nc; } void mincost(int city) { int i,ncity; completed[city]=1; cout<<city+1<<"--->"; ncity=least(city); if(ncity==999) { ncity=0; cout<<ncity+1; cost+=ary[city][ncity]; return; } mincost(ncity); } int main() { takeInput(); cout<<"\n\nThe Path is:\n"; mincost(0); //passing 0 because starting vertex cout<<"\n\nMinimum cost is "<<cost; return 0; } |

Comment below if you found any information incorrect or have doubts regarding Travelling Salesman Problem algorithm.

Hi,

Nicely explained. I was just trying to understand the code to implement this. What I was not able to understand is why we are adding the return to the same node as well for the minimum comparison.

Will the below changed least code not work for all situation ?

int least(int c)

{

int i,nc=999;

int min=999,kmin;

for(i=0;i < n;i++)

{

if((ary[c][i]!=0)&&(completed[i]==0))

if(ary[c][i] < min) /* REPLACED */

{

min=ary[c][i]; /* REPLACED */

kmin=ary[c][i];

nc=i;

}

}

if(min!=999)

cost+=kmin;

return nc;

}

Hi

Good explanation (: But… is it posible to do TSP problem in C without the recursion?

Your Dynamic TSP-Code might not work correctly for more than 4 cities.

Looping over all subsets of a set is a challenge for Programmers.

Is the code written using dynamic approach?

Isn’t this the branch and bound method?

what if I do not want him to go back to starting node ?

I’m pretty sure that this is just another implementation of the nearest neighbor algorithm….

it will be better if you could add more explanation about these above functions such as takeInput(), least(), minCost().

I am really hard to understand your code.

Nice..can i ask you something..how we want to assign a value of the array with specific value..is that possible for an array consists 2 value..its more like we put the coordinate in one array..

Thank you friend.

I was trying to implement one here and yours came to save my work. Now I’m sorry in the heuristic way. hugs

Att. Anderson

Itacoatiara – Amazonas – Brazil

I ran this for 10 cities. It ran fine, but total cost for my matrix of random costs was 138, which is higher than the 125 cost with another program which gave a result of 1 10 9 8 7 6 5 4 3 2 1, which is clearly not a valid calculation. Sigh…

The explanation is solid but the code is wrong.

In each recursion step only the closest next hop in regards to the starting city is calculated, but you really have to check ALL sub-problems. The recursion doesn’t do anything special here and could as well have been a for-loop.

Just check the following matrix where the start point 1 has a large cost to the furthest city 4:

“The cost list is:

0 1 1 99

1 0 1 1

1 1 0 1

99 1 1 0

The Path is:

1—>2—>3—>4—>1

Minimum cost is 102”

When obviously this could have been just 4 cost with 1->2->4->3->1

Dude checkout your code it does not work for all case;

int adj_matx[4][4] = {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}}; //ans: 80

int adj_matx[4][4] = {{0,4,1,3},{4,0,2,1},{1,2,0,5},{3,1,5,0}}; //ans: 7

int adj_matx[5][5] = {{0,100,300,100,75},{100,0,50,75,125},{300,50,0,100,125},{100,75,100,0,50},{75,125,125,50,0}}; //ans: 375

int adj_matx[4][4] = {{0,2,1,3},{2,0,4,100},{1,4,0,2},{3,100,2,0}}; //ans: 11

int adj_matx[4][4] = {{0,2,1,4},{2,0,4,3},{1,4,0,2},{4,3,2,0}}; //ans: 8

int adj_matx[4][4] = {{0,5,6,3},{5,0,3,6},{6,3,0,7},{3,6,7,0}}; //ans: 18

int adj_matx[5][5] = {{0,6,9,100,10},{6,0,11,100,100},{9,11,0,100,14},{100,100,100,0,8},{10,100,14,8,0}}; //ans:57

for the last case if starting node is 1 then path is 1-5-4-3-2-1 and cost is 135

Time complexity of given code is n!