C Program

Write a C program to solve Travelling Salesman problem for n cities using Heuristics.

#include<stdio.h>

void main() {

     int i;

int j;

int n;

int start;

int index;

int count = 1;

int min = 9999;

int min_dis = 0;

printf("Enter number of cities : ");

scanf("%d", &n);

int distance[n][n];

int visited[n];

int path[n];

for(i = 0; i < n; i++) {

for(j = 0; j < n; j++) {

printf("Enter element [%d][%d] : ", i, j);

scanf("%d", &distance[i][j]);

}

visited[i] = 0;

}

for(i = 0; i < n; i++) {

for(j = 0; j < n; j++) {

printf("%d\t", distance[i][j]);

}

printf("\n");

}

printf("\n");

printf("Enter start point %d to %d : ", 0, n-1);

scanf("%d", &start);

visited[start] = 1;

index = start;

path[0] = start;

while(count < n) {

i = index;

min = 9999;

         for(j = 0; j < n; j++) {

if(i == j || visited[j] == 1) {

continue;

}

else {

if(min > distance[i][j]) {

min = distance[i][j];

index = j;

}

}

}

i = index;

visited[index] = 1;

path[count] = index;

count++;

min_dis += min;

}

min_dis += distance[index][start];

path[count] = start;

for(i = 0; i < n; i++) {

printf("%d -> ", path[i]);

}

printf("%d\n", path[i]);

printf("\n");

printf("Minimum distance : %d\n", min_dis);

}

Output :