C++ Program to Implement Traveling Salesman Problem using Nearest Neighbour Algorithm

This C++ program implements the Travelling Salesman Problem which computes the minimum cost required to visit all the nodes by traversing across the edges only once.

Here is the source code of the C++ program to display the minimum cost by taking an undirected graph as input. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```

* C++ Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm

```
 */
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
using namespace std;
```
```
int c = 0,cost = 999;
```
```
int graph[4][4] = { {0, 10, 15, 20},
```
```
                    {10, 0, 35, 25},
```
```
                    {15, 35, 0, 30},
```
```
                    {20, 25, 30, 0}
```
```
                  };
```
```
void swap (int *x, int *y)
```
```
{
```
```
    int temp;
```
```
    temp = *x;
```
```
    *x = *y;
```
```
    *y = temp;
```
```
}
```
```
void copy_array(int *a, int n)
```
```
{
```
```
    int i, sum = 0;
```
```
    for(i = 0; i <= n; i++)
```
```
    {
```

        sum += graph[a[i % 4]][a[(i + 1) % 4]];

```
    }
```
```
    if (cost > sum)
```
```
    {
```
```
        cost = sum;
```
```
    }
```
```
}  
```
```
void permute(int *a, int i, int n) 
```
```
{
```
```
   int j, k; 
```
```
   if (i == n)
```
```
   {
```
```
        copy_array(a, n);
```
```
   }
```
```
   else
```
```
   {
```
```
        for (j = i; j <= n; j++)
```
```
        {
```
```
            swap((a + i), (a + j));
```
```
            permute(a, i + 1, n);
```
```
            swap((a + i), (a + j));
```
```
        }
```
```
    }
```
```
} 
```
```
int main()
```
```
{
```
```
   int i, j;
```
```
   int a[] = {0, 1, 2, 3};  
```
```
   permute(a, 0, 3);
```
```
   cout<<"minimum cost:"<<cost<<endl;
```
```
   getch();
```
```
}
```

Output
minimum cost:80

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Edmonds Karp Algorithm

» Next - C++ Program to Find Minimum Spanning Tree using Kruskal’s Algorithm

Next Steps:

Get Free Certificate of Merit in C++ Programming
Participate in C++ Programming Certification Contest
Become a Top Ranker in C++ Programming
Take C++ Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Recommended Articles: