Answer to Question #230629 in C for sky

Question

Take ‘n’ historic sites in Tamil Nadu as input. Design and implement a code in c language using brute force approach that identifies the shortest possible route for a traveller to visit these sites and come back to his starting point.

Answer 1

#include <stdio.h>
#define INFINITY 9999
#define MAX 10


void shortestPath(int g[MAX][MAX], int n, int start);


void shortestPath(int g[MAX][MAX], int n, int start) {
  int cost[MAX][MAX], distance[MAX], pred[MAX];
  int visited[MAX], count, mindistance, nextnode, i, j;


  // Creating cost matrix
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (g[i][j] == 0)
        cost[i][j] = INFINITY;
      else
        cost[i][j] = g[i][j];


  for (i = 0; i < n; i++) {
    distance[i] = cost[start][i];
    pred[i] = start;
    visited[i] = 0;
  }


  distance[start] = 0;
  visited[start] = 1;
  count = 1;


  while (count < n - 1) {
    mindistance = INFINITY;


    for (i = 0; i < n; i++)
      if (distance[i] < mindistance && !visited[i]) {
        mindistance = distance[i];
        nextnode = i;
      }


    visited[nextnode] = 1;
    for (i = 0; i < n; i++)
      if (!visited[i])
        if (mindistance + cost[nextnode][i] < distance[i]) {
          distance[i] = mindistance + cost[nextnode][i];
          pred[i] = nextnode;
        }
    count++;
  }


  // Printing the distance
  for (i = 0; i < n; i++)
    if (i != start) {
      printf("\nDistance from source to %d: %d", i, distance[i]);
    }
}
int main() {
  int g[MAX][MAX], i, j, n, u;
  n = 7;


  g[0][0] = 0;
  g[0][1] = 0;
  g[0][2] = 1;
  g[0][3] = 2;
  g[0][4] = 0;
  g[0][5] = 0;
  g[0][6] = 0;


  g[1][0] = 0;
  g[1][1] = 0;
  g[1][2] = 2;
  g[1][3] = 0;
  g[1][4] = 0;
  g[1][5] = 3;
  g[1][6] = 0;


  g[2][0] = 1;
  g[2][1] = 2;
  g[2][2] = 0;
  g[2][3] = 1;
  g[2][4] = 3;
  g[2][5] = 0;
  g[2][6] = 0;


  g[3][0] = 2;
  g[3][1] = 0;
  g[3][2] = 1;
  g[3][3] = 0;
  g[3][4] = 0;
  g[3][5] = 0;
  g[3][6] = 1;


  g[4][0] = 0;
  g[4][1] = 0;
  g[4][2] = 3;
  g[4][3] = 0;
  g[4][4] = 0;
  g[4][5] = 2;
  g[4][6] = 0;


  g[5][0] = 0;
  g[5][1] = 3;
  g[5][2] = 0;
  g[5][3] = 0;
  g[5][4] = 2;
  g[5][5] = 0;
  g[5][6] = 1;


  g[6][0] = 0;
  g[6][1] = 0;
  g[6][2] = 0;
  g[6][3] = 1;
  g[6][4] = 0;
  g[6][5] = 1;
  g[6][6] = 0;


  u = 0;
  shortestPath(g, n, u);


  return 0;
}