shortest.cpp

shortest path algorithm

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#define INF 10000
//INF - Infinity
//NULL = 0 (predefined)
const int SIZE=9; // No of nodes
char names[][2]={"A","B","C","D","E","F","G","H","I","J"};// node names

//Function to return the node no. given the name
int number(char name[])
{
 for(int i=0;i<SIZE;i++)
 if(strcmp(strupr(name),names[i])==0) return i;
 return 0;
}

//------------------------------------------
//Main search function - recursive. Returns path string
//parameters:
//	table     - Distance table
//	entry     - Entry point in the table (the rows)
//	exit      - Exit point in the table (the columns)
//	plength   - Path length. initially set to zero. weights are
//		    accumulated as we pass each node
//      hop_count - Maximum hops allowed = SIZE. decremented on every node

char* search(int table[SIZE][SIZE],int entry,int exit,int plength,int hop_count)
{
 static int min_length=INF;//static implies only one copy for all recursions
 char *temp,pstr[SIZE]="";
 if(hop_count==0) return NULL;//Return nothing if hop limit exceeded

 if(table[entry][exit]>0) // have we reached the exit node?
    {
     plength+=table[entry][exit];

     if(plength<min_length) //is current path shorter than previous minimum?
	{
	 min_length=plength;//if so replace
	 return names[entry];
	}
     return NULL;
    }
 // execute this section if exit node is not reached
 for(int i=0;i<SIZE;i++) //scan thru all exit paths
 {
  if(table[entry][i]>0) // Traverse only non-zero paths
  {
  //call recursive fn. store path string in a temporary variable
  temp=search(table,i,exit,plength+table[entry][i],hop_count-1);
  //accumulate path-length, decrement hop_count

  if(temp) strcpy(pstr,temp);// only accept valid paths
  }
 }

 //add current node to path before returning string
 if(strlen(pstr)>0) return strcat(pstr,names[entry]);

 return NULL;
}
//----------------------------------------------------------------

void main()
{
 int i,j;
 int dist_table[SIZE][SIZE]={{0,2,0,0,0,0,6,0},
			     {2,0,7,0,2,0,0,0},
			     {0,7,0,3,0,3,0,0},
			     {0,0,3,0,0,0,0,2},
			     {0,2,0,0,0,2,1,0},
			     {0,0,3,0,2,0,0,2},
			     {6,0,0,0,1,0,0,4},
			     {0,0,0,2,0,2,4,0}};//Distance matrix
 char spath[10],*sp,inp[2];
 int entry,exit;

 clrscr();
 // Cosmetic stuff here. To beautify
 cout<<"------- Distance Table ------\n\n  ";
 for(i=0;i<SIZE;i++)
 cout<<"  "<<names[i];
 cout<<"\n\n";

 for(i=0;i<SIZE;i++)
 {
  cout<<names[i]<<" ";
  for(j=0;j<SIZE;j++)
  cout<<"  "<<dist_table[i][j];
  cout<<"\n\n";
 }
 cout<<"\n\tEntry Node: ";cin.getline(inp,3);
 entry=number(inp);//convert name to number

 cout<<"\tExit Node: ";cin.getline(inp,3);
 exit=number(inp);//convert name to number

 //actual function call.pathlength initially set to zero. reqd for recursion
 sp=search(dist_table,entry,exit,0,SIZE);
 strcpy(spath,sp);
 cout<<"\n\tShortest Path is "<<strrev(spath)<<names[exit];
 //string reversal is reqd since fn returns path from dest to src

 getch();
}