C++ Program to Implement Nearest Neighbour Algorithm
Posted by Superadmin on August 08 2022 07:09:05

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)
Press return to continue