最短路径--迪杰斯特拉算法.txt

数据结构C对图的操作算法

void shortpath_DIJ(int ad[][M],int k,int pre[], //dist[ ]存放当前找到的从k到每个终点的最短路径长度，
                   int dist[],int n)  //求结点k到其余结点的最短路径；ad[][M]是图的邻接矩阵存储方式
{  int i,j,p,wm;   //pre[ ]表示从k到各终点的最短路径上，此顶点的前一顶点的序号；

   k=k-1; //数组的存储从0开始
   for(i=0;i<n;i++)
   {  dist[i]=ad[k][i];  //dist[ ]的初值是矩阵中的第k行
      if(dist[i]<MAX)  pre[i]=k+1; //若某结点和k结点直接连通，则此顶点的前一顶点的序号就是k；否则为0
      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];
         }//查找未被处理过的当前路径（权值）最小的结点在数组中的下标p

      if(p==-1)  break;
      else{  ad[p][p]=1; //对角线置为1，表示被处理
             for(i=0;i<n;i++)
                if(ad[i][i]==0)
                   if(dist[p]+ad[p][i]<dist[i]) //在矩阵刚确定的p行中查找与dist[p]的和小于dist[i]的结点
                   {  dist[i]=dist[p]+ad[p][i]; //修改此结点的对应最短路径（权值）的值
                      pre[i]=p+1; //pre[ ]存储从k到i的最短路径上前一顶点的序号；
                   }
          }
   }
}