You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
61 lines
1.3 KiB
C++
61 lines
1.3 KiB
C++
/*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.*/
|
|
|
|
#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;
|
|
}
|
|
|
|
/*
|
|
|
|
minimum cost:80
|