Program for Travelling Salesman Problem in C

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