Travelling Salesman Problem in C and C++

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 (nn) 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

Travelling Salesman Problem (TSP)

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 ith node finding remaining minimum distance to that ith node is a sub-problem.

If we solve recursive equation we will get total (n-1) 2(n-2)  sub-problems, which is O (n2n).

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

Therefore total time complexity is O (n2n) * O (n) = O (n22n)

Space complexity is also number of sub-problems which is O (n2n)

Program for Travelling Salesman Problem in C

#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++

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

49 thoughts on “Travelling Salesman Problem in C and C++”

  1. 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;
    }

      1. hellow mam your code is not work properly (for selecting minimum path)
        because i insert a cost matrix
        input 0 7 3
        4 0 2
        9 1 0
        this cost matrix currect answer is==>8 and also travel a vertex in
        1–>3–>2–>1
        But your code is only work with a order wise selection
        example
        it will travel only with 1–>2–>3–>1.
        etc…………….

        1. ihatefakeindianprogrammers

          Are you for real? Are you that dumb?

          this is an undirected graph.
          1->3->2->1 is exactly the same as 1->2->3->1.

          go ahead, bob your head.

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

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

      It doesn’t. I tried it for 6 and it fails to find the minimum path.
      Example cost matrix and found path:

      The cost list is:
      0 5 9 12 4 8
      5 0 4 7 9 7
      9 4 0 5 5 11
      12 7 5 0 10 14
      4 9 5 10 0 12
      8 7 11 14 12 0

      The Path is:
      1—>5—>3—>2—>6—>4—>1 (cost 46)

      But the path 1->2->3->4->5->6->1 has cost 44

      1. This code is NOT correct. Also every other site has this same exact code.
        Some one please share the link to a correct working code for solving TSP using Dynamic Programming approach.

        1. min=ary[i][0]+ary[c][i]; has to be min=ary[i][c]+ary[c][i]; this migth solve the issue with the above code

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

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

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

  6. Benjamin Thurston

    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…

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

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

      1. I second that. Saurabh is correct.

        ———————-T ( 1,{ 2 3 4 5 })———————
        Pairwise cost
        { 6 9 100 10 }
        Subproblem cost
        { 129 128 39 125 }
        Sum cost
        { 135 137 139 135 }
        Sub Paths
        Printing Matrix
        5 4 3 2
        2 4 5 3
        2 3 5 4
        2 3 4 5
        Choosing subpath 0
        Path Vector
        { 5 4 3 2 1 }

  9. I have never commented on any website. But i was compelled to do so this time. I have been reading your blog for a long time and i find explanations and code far easier than other websites. It’s amazing and very helpful.

  10. 0 9 8 8
    12 0 13 6
    10 9 0 5
    20 15 10 0

    for this matrix the solution should be 35 (1-2-4-3-1)but by using this code it give 40(1-3-4-2-1).
    and also this approach is not dynamic it is greedy.

  11. The Algorithm has this result :
    The cost list is:
    0 10 15 20
    10 0 35 25
    15 35 0 30
    20 25 30 0

    The Path is:
    1—>;2—>;3—>;4—>;1

    Minimum cost is 95
    But the correct minimum cost is 80
    and the correct path is 1–>2–>4–>3–>1

  12. It is not working correctly for testcase
    4
    0 5 15 15
    5 0 3 7
    15 3 0 10
    15 7 10 0
    Output is : 1—>2—>4—>3—>1
    cost 37
    Output should be: 1—>2—>3—>4—>1
    cost 33

  13. Pragun Hagaldivte

    Hi, I’m sorry but your code is wrong.
    Please make the required changes or at least remove the code.

  14. Shreyaskar Verma

    I mean how can you be so wrong?You wrote the explanation so nicely(probably you copied that too) and then this shit code which is present all over the internet just for wasting our time.Dont create such rubbish posts if you dont know how to implement the algorithm.

Leave a Comment

Your email address will not be published. Required fields are marked *