$ g++ TSPNearestNeighbour.cpp $ a.out minimum cost:80 ------------------ (program exited with code: 0) Press return to continue
Users Online
· Guests Online: 101
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Newest Threads
No Threads created
Hottest Threads
No Threads created
Latest Articles
Articles Hierarchy
C++ Program to Implement Nearest Neighbour Algorithm
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.
-
#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;
-
}
Output:
Comments
No Comments have been Posted.
Post Comment
Please Login to Post a Comment.