/* 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
#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