TSP in C Programming

ALGORITHM

TSP in C Programming

#include
#include

#define MAX 9

struct Tour
{
int iCost;
int iCount;
// int aiCity[MAX];
int aiVisit[MAX];
}cTour,oTour;

int fnVisited(int adj)
{
int iI;
for(iI=0;iI
if(cTour.aiVisit[adj]==adj)
return 1;
return 0;
}

void OptimalTour(int iCity,int iCost,int iN,int aiCost[MAX][MAX])
{
int iI;
// printf("/nHai");
cTour.iCost +=iCost;
cTour.aiVisit[cTour.iCount]=0;
// printf("\ncTour.iCount : %d",cTour.iCount);
if(cTour.iCost
{
oTour.iCost=cTour.iCost;
oTour=cTour;
}
printf("\nCost is : %d",cTour.iCost);
printf("\nPaths are : %d \n",cTour.iCount);
for(iI=0;iI<=cTour.iCount;iI++)
{
printf(" %d ",cTour.aiVisit[iI]);
// getch();
}
// cTour.iCount--;
// cTour.aiVisit[cTour.iCount]=-1;
cTour.iCost-=aiCost[iCity][0];
cTour.iCount--;
}


void fnTsp(int iCity,int iCost,int iN,int aiCost[MAX][MAX])
{
int adj;
cTour.iCost +=iCost;
cTour.aiVisit[cTour.iCount++]=iCity;
if(cTour.iCount==iN && aiCost[iCity][0]!=999)
{
OptimalTour(iCity,aiCost[iCity][0],iN,aiCost);
getch();
}
else
{
for(adj=1;adj
if(!fnVisited(adj) && cTour.iCost+aiCost[adj][iCity]
fnTsp(adj,aiCost[adj][iCity],iN,aiCost);
}
cTour.iCost -=iCost;
cTour.aiVisit[cTour.iCount]=-1;
cTour.iCount-=1;
}

void main()
{
int iN,aiCost[MAX][MAX];

int iI,iJ;

clrscr();
printf("Enter the number of nodes : ");
scanf("%d",&iN);
printf("\nEnter the cost matrix\n");
for(iI=0;iI
for(iJ=0;iJ
scanf("%d",&aiCost[iI][iJ]);
for(iI=0;iI
cTour.aiVisit[iI]=-1;
cTour.iCost=0;
cTour.iCount=0;
oTour.iCost=999;
fnTsp(0,0,iN,aiCost);
getch();
}