# C++ Program to Implement Nearest Neighbour Algorithm

This is a C++ Program to implement nearest neighbour algorithm to solve TSP. 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 source code of the C++ Program to Implement Nearest Neighbour Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include<stdio.h>`
2. `#include<conio.h>`
3. `#include<iostream>`
4. ` `
5. `using namespace std;`
6. ` `
7. `int c = 0, cost = 999;`
8. `int graph[4][4] = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, {`
9. `        20, 25, 30, 0 } };`
10. ` `
11. `void swap(int *x, int *y)`
12. `{`
13. `    int temp;`
14. `    temp = *x;`
15. `    *x = *y;`
16. `    *y = temp;`
17. `}`
18. `void copy_array(int *a, int n)`
19. `{`
20. `    int i, sum = 0;`
21. `    for (i = 0; i <= n; i++)`
22. `    {`
23. `        sum += graph[a[i % 4]][a[(i + 1) % 4]];`
24. `    }`
25. `    if (cost > sum)`
26. `    {`
27. `        cost = sum;`
28. `    }`
29. `}`
30. `void permute(int *a, int i, int n)`
31. `{`
32. `    int j, k;`
33. `    if (i == n)`
34. `    {`
35. `        copy_array(a, n);`
36. `    }`
37. `    else`
38. `    {`
39. `        for (j = i; j <= n; j++)`
40. `        {`
41. `            swap((a + i), (a + j));`
42. `            permute(a, i + 1, n);`
43. `            swap((a + i), (a + j));`
44. `        }`
45. `    }`
46. `}`
47. `int main()`
48. `{`
49. `    int i, j;`
50. `    int a[] = { 0, 1, 2, 3 };`
51. `    permute(a, 0, 3);`
52. `    cout << "minimum cost:" << cost << endl;`
53. `}`

Output:

```\$ g++ TSPNearestNeighbour.cpp
\$ a.out

minimum cost:80

------------------
(program exited with code: 0)

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