shortpaht.h

数据库课程设计 导航 其实就是Dijkstra算法的应用

enum{False,True};
void checkPath(LHList<Unit *> &message,int **points,int rowNumber)
{
  char from,to;//起始地点
  cout<<"input start unit symbol"<<endl
	  <<"From "; 
  cin>>from; 
  if(from>96)
    from=from-32;
  cout<<"input end unit symbol"<<endl
	  <<"to "; 
  cin>>to; 
  if(to>96)
    to=to-32;
  int start=from-65;//开始点
  int end=to-65;//结束点
  int min=MAX; 
  int w;
  int *final=new int[rowNumber]; //记录点是不是被访问过
  int *ShortPathLength=new int[rowNumber]; //最短距离 
  int **allPath=new int*[rowNumber]; //记录所有路径  
	for(int i=0;i<rowNumber;i++)
	{
	 allPath[i]=new int[rowNumber];
	}  

  for(int v=0;v< rowNumber;v++)//初始化
  {
	  final[v]=False;
	  ShortPathLength[v]=points[start][v];  
	  for(w=0;w<rowNumber;w++)
		  allPath[v][w]=-1;
	  allPath[v][0]=start;
	  if(points[start][v]<MAX)
	   allPath[v][1]=v;
  } 
   final[start]=True;
   ShortPathLength[start]=0;

   for(i=1;i<rowNumber;i++)
   {
	 min=MAX;
     for( w=0;w<rowNumber;w++)//找到最小值
		 if(!final[w])
		 { 				 	
			 if(ShortPathLength[w]<min)
			 {
			  v=w; 
			  min=ShortPathLength[w];
			 }
		 }
	  final[v]=True;            //起点
	  if(v==end)                //找到终点
		  break;
	 for( w=0;w<rowNumber;w++)
	 { 
	   if(!final[w]&&(min+points[v][w])<ShortPathLength[w])
	   {	
		   ShortPathLength[w]=min+points[v][w]; 
		   for(int k=0;k<i+1;k++)//拷贝路径
		   allPath[w][k]=allPath[v][k]; 
		   allPath[w][i+1]=w;	//加上当前点	  
	   }
	 } 
   }  
    printf("%c ->%c 路径如下： ",start+65,end+65);
	  for(w=0;w<rowNumber;w++)
	  {
		if(allPath[end][w]!=-1)
	    printf("%c ->",allPath[end][w]+65);
	  }
   cout<<endl<<"总路长为："<<ShortPathLength[end]<<endl;
 /* for( v=0;v< rowNumber;v++)
   { 
	   printf("%c ->%c  ",start+65,v+65);
	  for(w=0;w<rowNumber;w++)
	  {
		if(allPath[v][w]!=-1)
	   printf("%c ",allPath[v][w]+65);
	  }
	  cout<<" "<<ShortPathLength[v]<<endl;
   } //*/
   cout<<endl<<endl
	  <<"===================================继续==============================="
	  <<endl;
  message.printList();
  cout<<"Check Unit message input M"
	   <<"\tCheck path input P"
	   <<"\tExit input Q"
	   <<endl;
}