ch6_5.txt

来自「数据结构（ C语言版） 讲义daima 数据结构（ C语言版） 讲义dai」· 文本 代码 · 共 28 行

void shortpath_DIJ(int ad[][M],int k,int pre[],
                   int dist[],int n)
{  int i,j,p,wm;
   k=k-1;
   for(i=0;i<n;i++)
   {  dist[i]=ad[k][i];
      if(dist[i]<MAX)  pre[i]=k+1;
      else             pre[i]=0;
   }
   pre[k]=0; dist[k]=0; ad[k][k]=1;
   for(j=0;j<(n-1);j++)
   {  wm=MAX;  p=-1;
      for(i=0;i<n;i++)
         if((ad[i][i]==0)&&(dist[i]<wm))
         {   p=i;
             wm=dist[i];
         }
      if(p==-1)  break;
      else{  ad[p][p]=1;
             for(i=0;i<n;i++)
                if(ad[i][i]==0)
                   if(dist[p]+ad[p][i]<dist[i])
                   {  dist[i]=dist[p]+ad[p][i];
                      pre[i]=p+1;
                   }
          }
   }
}