Program
#include <stdio.h>
#include <conio.h>
int s, c[100][100], ver;
float optimum = 999, sum;
/* function to swap array elements */
void swap(int v[], int i, int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}
/* recursive function to generate permutations */
void brute_force(int v[], int n, int i)
{
// this function generates the permutations of the array from element i to element n-1
int j,sum1,k;
// if we are at the end of the array, we have one permutation
if (i == n)
{
if (v[0] == s)
{
for (j = 0; j < n; j++)
printf("%d ", v[j]);
sum1 = 0;
for (k = 0; k < n - 1; k++)
{
sum1 = sum1 + c[v[k]][v[k + 1]];
}
sum1 = sum1 + c[v[n - 1]][s];
printf("sum = %d\n", sum1);
getch();
if (sum1 < optimum)
optimum = sum1;
}
}
// recursively explore the permutations starting at index i going through index n-1//
else
{
for (j = i; j < n; j++)
{
/* try the array with i and j switched */ swap(v, i, j);
brute_force(v, n, i + 1);
}
}
}
void nearest_neighbour(int ver)
{
int min, p, i, j, vis[20], from;
for (i = 1; i <= ver; i++)
vis[i] = 0;
vis[s] = 1;
from = s;
sum = 0;
for (j = 1; j < ver; j++)
{
min = 999;
for (i = 1; i <= ver; i++)
if (vis[i] != 1 && c[from][i] < min && c[from][i] != 0)
{
min = c[from][i];
p = i;
}
vis[p] = 1;
from = p;
sum = sum + min;
}
sum = sum + c[from][s];
}
void main()
{
int ver, v[100], i, j;
printf("\n*********************************************************");
printf("\n*********************************************************");
printf("\n** Program for Travelling Salesman Problem in C **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n*********************************************************");
printf("\n*********************************************************");
printf("\nEnter n : ");
scanf("%d", &ver);
for (i = 0; i < ver; i++)
v[i] = i + 1;
printf("Enter cost matrix\n");
for (i = 1; i <= ver; i++)
{
for (j = 1; j <= ver; j++)
scanf("%d", &c[i][j]);
}
printf("\nEnter source : ");
scanf("%d", &s);
brute_force(v, ver, 0);
printf("\nOptimum solution with brute force technique is=%f\n", optimum);
nearest_neighbour(ver);
printf("\nSolution with nearest neighbour technique is=%f\n", sum);
printf("The approximation val is=%f", ((sum / optimum) - 1) * 100);
printf(" % ");
getch();
}
Output
********************************************************* ********************************************************* ** Program for Travelling Salesman Problem in C ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** ********************************************************* ********************************************************* Enter n : 3 Enter cost matrix 1 2 4 4 5 9 2 6 8 Enter source : 3 3 1 2 sum = 13 3 2 1 sum = 14 Optimum solution with brute force technique is=13.000000 Solution with nearest neighbour technique is=13.000000 The approximation val is=0.000000