Thursday, 1 May 2014

traveling salesman person problem program in c

/* TRAVELLING SALES PERSON created by prashant shinde*/
#include<conio.h>
#include<stdio.h>
#define MAX 10
typedef struct
{
 int nodes[MAX];
 int vertex;
 int min;
}Path_node;
Path_node TSP(int source ,Path_node list,int Element[][MAX],int max_no_cities)
{
 int i,j;
 Path_node new_list,new_path,new_min;
 if(list.vertex==0)
 {
   new_min.min=Element[source][1];
   new_min.nodes[max_no_cities-1]=source;
   new_min.vertex=max_no_cities;
   return new_min;
 }
 for(i=0;i<list.vertex;i++)
 {
   new_list.vertex=0;
   for(j=0;j<list.vertex;j++)
     if(i!=j)
     new_list.nodes[new_list.vertex++]=list.nodes[j];
     new_path=TSP(list.nodes[i],new_list,Element,max_no_cities);
     new_path.min=Element[source][list.nodes[i]]+new_path.min;
     new_path.nodes[max_no_cities-list.vertex-1]=source;
     if(i==0)
       new_min=new_path;
     else
       if(new_path.min<new_min.min)
 new_min=new_path;
   }
   return new_min;
 }
 void display(Path_node Path)
 {
    int i;
    printf("\n\nThe minimum cost is %d\n",Path.min);
    printf("\n The path is...\n");
    for(i=0;i<Path.vertex;i++)
    printf("%d--",Path.nodes[i]);
    printf("%d",Path.nodes[0]);
 }
 void main()
 {
    int i,j,Element[MAX][MAX],max_no_cities;
    Path_node Graph,Path;
    clrscr();
    printf("\n How many Number of Cities are There?");
    scanf("%d",&max_no_cities);
    if(max_no_cities==0)
    {
       printf("Error:There is no city for processing the TSP");
    }
    else
    {
       for(i=1;i<=max_no_cities;i++)
       {
for(j=1;j<=max_no_cities;j++)
   if(i==j)
      Element[i][j]=0;
   else
   {
     printf("Enter distance from city%d to %d ?",i,j);
     scanf("%d",&Element[i][j]);
   }
   if(i>1)
     Graph.nodes[i-2]=i;
}
Graph.vertex=max_no_cities-1;
Path=TSP(1,Graph,Element,max_no_cities);
display(Path);
     }
     getch();
   }
OUTPUT:

 How many Number of Cities are There?4
Enter distance from city1 to 2 ?2
Enter distance from city1 to 3 ?9
Enter distance from city1 to 4 ?10
Enter distance from city2 to 1 ?1
Enter distance from city2 to 3 ?6
Enter distance from city2 to 4 ?4
Enter distance from city3 to 1 ?15
Enter distance from city3 to 2 ?7
Enter distance from city3 to 4 ?8
Enter distance from city4 to 1 ?6
Enter distance from city4 to 2 ?3
Enter distance from city4 to 3 ?12


The minimum cost is 21

 The path is...
1--3--4--2--1





























No comments:

Post a Comment