//最短路徑(狄克斯特拉算法)PshortP.h
//從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑
void PShortPath(AdjMatrix &G,int v0,int dist[],int path[])
//網(wǎng)G從下標(biāo)v0到其他頂點(diǎn)的最短距離dist和最短路徑下標(biāo)path
{int n=G.NumV();
 int *s=new int[n];
 int mindis,i,j,u;
 for(i=0;i<n;i++)
 {dist[i]=G.GetWeight(v0,i);
  s[i]=0;
  if(i!=v0&&dist[i]<MaxValue) path[i]=v0;
  else path[i]=-1;
 }
 s[v0]=1;//標(biāo)記頂點(diǎn)v0已從集合T加入到集合S中
 //在當(dāng)前還未找到最短路徑的頂點(diǎn)集中選取具有最短距離的頂點(diǎn)u
 for(i=1;i<n;i++)
 {mindis=MaxValue;
  for(j=0;j<n;j++)
   if(s[j]==0&&dist[j]<mindis)
    {u=j;
     mindis=dist[j];
    }
  //當(dāng)已不再存在路徑時(shí)算法結(jié)束;此語(yǔ)句對(duì)非連通圖是必需的
  if(mindis==MaxValue) return;
  s[u]=1;//標(biāo)記頂點(diǎn)u已從集合T加入到集合S中
  //修改從v0到其他頂點(diǎn)的最短距離和最短路徑
  for(j=0;j<n;j++)
   if(s[j]==0&&G.GetWeight(u,j)<MaxValue&&
    dist[u]+G.GetWeight(u,j)<dist[j])
   {//頂點(diǎn)v0經(jīng)頂點(diǎn)u到其他頂點(diǎn)的最短距離和最短路徑
    dist[j]=dist[u]+G.GetWeight(u,j);
    path[j]=u;
   }
 }
}