shortpath.txt

求最短路径

 shortpath最短路径
 
 
  
 
 #include<iostream.h>
const int N=9;
const int Max=32567;
int A[N][N];
int dis[N];
int path[N];
int Path[N];
int begin=0;
void Init()
{
 int i;
 int j;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   A[i][j]=0;
 A[0][1]=20;
 A[0][2]=5;
 A[0][3]=30;
 A[0][4]=40;
 A[1][2]=10;
 A[1][3]=30;
 A[2][3]=15;
 A[2][4]=30;
 A[2][5]=50;
 A[3][5]=15;
 A[3][6]=100;
 A[4][6]=60;
 A[4][7]=32;
 A[5][6]=70;
 A[6][7]=40;
 A[6][8]=25;
 A[7][8]=32;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++) 
   if(A[i][j]==0)
    A[i][j]=Max;
   else 
    cout<<i<<"----"<<A[i][j]<<"----->"<<j<<'\t';
   cout<<endl;
   for(i=0;i<N;i++)
    path[i]=0;
   for(i=0;i<N;i++)
   {
    dis[i]=A[begin][i];
   }
}
int Minpath()
{
 int j=0;
 int s=0;
 int min=Max;
 while(j<N)
 {
  if(dis[j]<min&&path[j]==0)
  {
   min=dis[j];
   s=j;
  }
  j++;
 }
 if(s<Max)
 return s;
 j=0;
 while(path[j]!=0)
  j++;
 return j;
} 
void Short_path()
{
 int i=1;
 int j;
 int nextv;
 path[begin]=1;
 Path[0]=begin;
 while(i<N)
 {
  nextv=Minpath();
  path[nextv]=1;
  Path[i]=nextv;
  for(j=0;j<N;j++)
  {
   if(path[j]==0)
   {
    for(int jj=0;jj<N;jj++)
    {
     if(path[jj]&&jj!=begin)
     {
      if(dis[jj]+A[jj][j]<dis[j])
      {
       dis[j]=dis[jj]+A[jj][j];
      }
     }
    }
   }
  }
  i++;
 }
}
void Print()
{
 int i;
 cout<<" The short path is : \n ";
 for(i=0;i<N;i++)
 {
  if(i==N-1)
   cout<<Path[i]<<endl;
  else
   cout<<Path[i]<<"------->";
 }
}
void main()
{
 Init();
 Short_path();
 Print();
}