/*******************************************
* Name: Peter Kaminsky
* Course: Adv. C
* Assingment: Traveling Salesman
* Compiler: Div-C++
*******************************************/
#include <stdio.h>
#include <math.h>
#include <time.h>
//#define PERCENT //doesn't work corrently
#define SPIN //doesn't refresh enough when there are too many cities
void starter(int array[][], int size_of_array, long long int TotPaths);
void depth (int array[][], int size_of_array, intCol, intTot, char string[],
char Min_Path[], int *Min_Length,
long long int TotPaths, int Depth);
long long factorial (long long n);
FILE *f;
int step=1;
main()
{ char meh;
/*
#define ASIZE 5
int a[][ASIZE]={ { 0,29, 5,20,15},
{29, 0,42,24,35},
{ 5,42, 0, 8,38},
{20,24, 8, 0, 4},
{15,35,38, 4, 0} };
*/
/*
#define ASIZE 10
int a[][ASIZE]={ { 0,30,39,24,11,27,30,26, 3,31},
{30, 0,11, 3,36,32,20, 1,48,50},
{39,11, 0, 7,41,50,13,34, 9,12},
{24, 3, 7, 0,31,31,46,24,25,23},
{11,36,41,31, 0,29,12,10,28,34},
{27,32,50,31,29, 0,47,15, 8,42},
{30,20,13,46,12,47, 0, 2,22, 3},
{26, 1,34,24,10,15, 2, 0,10,10},
{ 3,48, 9,25,28, 8,22,10, 0,20},
{31,50,12,23,34,42, 3,10,20, 0} };
*/
/*
#define ASIZE 13 //has two paths!
int a[][ASIZE]={ { 0,37, 6, 7,14,32,34,37,31, 7,42, 8,14},
{37, 0,35,14,46,47, 6,44, 3,17,28,39, 8},
{ 6,35, 0,14,41,23,12,35, 3,28,25,45,50},
{ 7,14,14, 0,33,21,24,27,23,16,29, 2,45},
{14,46,41,33, 0, 7,46,42,14,19,43, 7, 3},
{32,47,23,21, 7, 0,25,40,37,36,26,48,44},
{34, 6,12,24,46,25, 0, 7,44,31,23, 6,33},
{37,44,35,27,42,40, 7, 0,10,29,25,44, 7},
{31, 3, 3,23,14,37,44,10, 0,35,34, 8,10},
{ 7,17,28,16,19,36,31,29,35, 0,14,25,11},
{42,28,25,29,43,26,23,25,34,14, 0,19,47},
{ 8,39,45, 2, 7,48, 6,44, 8,25,19, 0,39},
{14, 8,50,45, 3,44,33, 7,10,11,47,39, 0} };
*/
#define ASIZE 15
int a[][ASIZE]={ { 0,12,38,44,47,23,33,13,13,39,50,33, 7,20,29},
{12, 0,31,27,21, 6,10,36,19,40,13,12, 1, 2,25},
{38,31, 0,39,14,39,32,23,47,25,10, 7,40, 4,25},
{44,27,39, 0,12,50,12, 9,35,38,19,42, 8, 7, 6},
{47,21,14,12, 0,11,32,23,29,42,29,26,48,25,25},
{23, 6,39,50,11, 0,28,46,10,44,40,40, 4,16,19},
{33,10,32,12,32,28, 0,20, 6,35,42, 6,37, 3,29},
{13,36,23, 9,23,46,20, 0,48,19,45,28,27, 9, 3},
{13,19,47,35,29,10, 6,48, 0,36, 4,29,19,16,22},
{39,40,25,38,42,44,35,19,36, 0,14,18,40, 4,36},
{50,13,10,19,29,40,42,45, 4,14, 0, 9,18, 6,32},
{33,12, 7,42,26,40, 6,28,29,18, 9, 0,36, 4,33},
{ 7, 1,40, 8,48, 4,37,27,19,40,18,36, 0,46, 2},
{20, 2, 4, 7,25,16, 3, 9,16, 4, 6, 4,46, 0,25},
{29,25,25, 6,25,19,29, 3,22,36,32,33, 2,25, 0} };
/*
#define ASIZE 20
int a[][ASIZE]={ { 0,12,40,37,18,15, 5,17,49,11, 4,40,18,46,37,25,14,40,30,44},
{12, 0,32, 5,47,48,21,29,45,31,16, 4,44,22,31,18,47,14,50,24},
{40,32, 0,11,37,41,49,14,29,41,23,20,42,41,14,46,47,28,41,19},
{37, 5,11, 0,37,30,40,47,19, 1,21,40, 6,12, 6,42,14,24,13, 7},
{18,47,37,37, 0,29,21, 8,34, 9,18,37, 1,42,45, 2,48,48,11,25},
{15,48,41,30,29, 0,20,38,33,22,12,11,47,14,26, 9,22, 2, 7,27},
{ 5,21,49,40,21,20, 0, 4,42,39,13,21,19,11,38,47,13,20,45,43},
{17,29,14,47, 8,38, 4, 0,21,38,36,43,30,47,49,35,27,20,47,20},
{49,45,29,19,34,33,42,21, 0,23, 5,27, 3,23,14, 7,18,44,49,25},
{11,31,41, 1, 9,22,39,38,23, 0, 6, 9,16,24,29, 6,11,37, 3, 4},
{ 4,16,23,21,18,12,13,36, 5, 6, 0,27,28,39,33,50,45,50,14,35},
{40, 4,20,40,37,11,21,43,27, 9,27, 0, 3, 7,29, 9,36,33,11,48},
{18,44,42, 6, 1,47,19,30, 3,16,28, 3, 0,40,19, 9,23,18,49,22},
{46,22,41,12,42,14,11,47,23,24,39, 7,40, 0,33,39, 4, 7,22,35},
{37,31,14, 6,45,26,38,49,14,29,33,29,19,33, 0,12,48, 7,44,17},
{25,18,46,42, 2, 9,47,35, 7, 6,50, 9, 9,39,12, 0, 6, 1,36,22},
{14,47,47,14,48,22,13,27,18,11,45,36,23, 4,48, 6, 0,34,31,34},
{40,14,28,24,48, 2,20,20,44,37,50,33,18, 7, 7, 1,34, 0,16, 3},
{30,50,41,13,11, 7,45,47,49, 3,14,11,49,22,44,36,31,16, 0,34},
{44,24,19, 7,25,27,43,20,25, 4,35,48,22,35,17,22,34, 3,34, 0} };
*/
int i, j, size=sqrt((sizeof(a)/sizeof(int)));
printf("Cities: %d\n",size);
printf("Segments between cities: %d\n",((size*size-size)/2)); //cities choose 2
long long int TotPaths=factorial(size-1);
printf("Posible paths: %.0f\n", (float)TotPaths);
long int startT=clock(); //start timer
starter(a,size,TotPaths);//call function
long int stopT=clock(); //stop timer
printf("%c\nSearch Time: %.2f Seconds",13,(float)(stopT-startT)/CLK_TCK);
printf("\n\nPress a key to close this window.");
meh=getch();
}//end main()
void starter(int a[][], int size, long long TotPaths)
{ int minlen=0;
char minpath[100]={};
depth (a, size, 0, 0, "A", minpath, &minlen, TotPaths, 0);
printf("%cThe shortest path has a length of %d\n",13,minlen); //Print the Total Length
printf("All of the shortest (directional) paths are:\n\n");
/*Print the Paths*/
f=fopen("minTemp.txt","r");
while(fgets(minpath,size,f)!=NULL)
fputs(minpath,stdout);
fclose(f);
}//end starter()
void depth (int a[][ASIZE], int size, int Old_Col, intTot, char Old_Str[],
char minpath[], int *minlen, long long int TotPaths, int Depth)
{ int i, j, row=Old_Col, col, stop=1;
static long long int paths=0;
char string[100]={}, sub[0]={}; /** create a new private string for the path **/
strcpy(string,Old_Str); /** copy the old path to the new string **/
sprintf(sub,"%c",Old_Col+65); /** find new city letter **/
if(strrchr(string,sub[0])==NULL) /** don't double-up on the print command **/
strcat(string,sub); /** add the new city to the new string **/
a[Old_Col][Old_Col]=-1; //came from this city, can't go back to it
/************************************//// start end-of-the-line block
/**/ for(i=0; i<size; i++) //check for the end-of-the-line
/**/ if(a==0)
/**/ stop=0;
/**/ if(stop==1) //if this IS the end-of-the-line
/**/ { Tot+=a[0][Old_Col]; //go back to city 'A'
#ifdef PERCENT //switch the printing of the % on/off
/**/ paths++; //the number of paths already taken
/**/ printf("%c%3.2f%c ",13,((float)paths*100/TotPaths),37);
#endif //there is something wrong with paths count
#ifdef SPIN //switch the spining thing on/off
/**/ switch(step) //because... I can
/**/ { case 1: { printf("%c\\",8); step=2; break; }// this needs to go more often,
/**/ case 2: { printf("%c|",8); step=3; break; }// when there are more cities
/**/ case 3: { printf("%c/",8); step=4; break; }// it doesn't get
/**/ case 4: { printf("%c-",8); step=1; break; }// triggered enough
/**/ }
#endif
/**/ if( (Tot==*minlen) ) //store current "minpath" to a file
/**/ { f=fopen("minTemp.txt","a"); //and other "minlen" paths
/**/ fprintf(f,"%s\n",string); //
/**/ fclose(f); //when there is a new "minpath"
/**/ } //start the file over again
/**/ if( ((*minlen==0) || (Tot<*minlen)) ) //
/**/ { *minlen=Tot; //at the very end,
/**/ strcpy(minpath,string); //print the real shortest paths
/**/ f=fopen("minTemp.txt","w"); //from the file
/**/ fprintf(f,"%s\n",string); //
/**/ fclose(f); //
/**/ }
/**/ }
/************************************//// end end-of-the-line block
for(col=0; col<size; col++) //step through all unvisited cities
{ if( a[col][col]!=-1 ) //continue if the current length is shorter
{ if(((Tot+a[row][col])<*minlen) || *minlen==0)
{ depth(a,size,col,Tot+a[row][col],string,minpath,minlen,TotPaths,++Depth);
a[col][col]=0; //this city is now back 'open'
Depth--; //came back a level
}
#ifdef PERCENT //switch the printing of the % on/off
else //something is wrong with paths count
{ paths+=( factorial(size-Depth-1) ); //this should be the number of paths that
} //would have been searched through but weren't because the current path
#endif//was longer then the current "shortest path"
}
}
}//end depth()
long long factorial(long long n) //a "long long" O_o? crazy
{ if(n==1)
return(1);
else
return(n * factorial(n-1));
}
