//最短路徑(狄克斯特拉算法)PshortP1.cpp
//從一個頂點到其余各頂點的最短路徑
#include<iostream.h>
#include<iomanip.h>
#include "graph.cpp"
void PShortPath(AdjMatrix G,int v0,int dist[],int path[])
//網(wǎng)G從下標(biāo)v0到其他頂點的最短距離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)記頂點v0已從集合T加入到集合S中
 //在當(dāng)前還未找到最短路徑的頂點集中選取具有最短距離的頂點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)已不再存在路徑時算法結(jié)束;此語句對非連通圖是必需的
  if(mindis==MaxValue) return;
  s[u]=1;//標(biāo)記頂點u已從集合T加入到集合S中
  //修改從v0到其他頂點的最短距離和最短路徑
  for(j=0;j<n;j++)
   if(s[j]==0&&G.GetWeight(u,j)<MaxValue&&
    dist[u]+G.GetWeight(u,j)<dist[j])
   {//頂點v0經(jīng)頂點u到其他頂點的最短距離和最短路徑
    dist[j]=dist[u]+G.GetWeight(u,j);
    path[j]=u;
   }
 }
}
//算法測試
void main()
{cout<<"PShortP1.cpp運行結(jié)果:\n";
 int n=6,k1=1,k2=1;
 AdjMatrix g(n,k2);
 g.CreateMatrix(n,k1,k2);
 g.Creatgraph(n,k2);
 int m=g.NumV();
 int *dist=new int[m];
 int *path=new int[m];
 int v0=0;
 PShortPath(g,v0,dist,path);
 cout<<"從頂點"<<g.GetValue(v0)
     <<"到其他各頂點的最短距離為:\n";
 for(int i=0;i<m;i++)
  cout<<"到頂點"<<g.GetValue(i)
      <<"的最短距離為:"<<dist[i]<<endl;
 cout<<"從頂點"<<g.GetValue(v0)
     <<"到其他各頂點的最短路徑的前一頂點為:\n";
 for(int i=0;i<m;i++)
  if(path[i]!=-1)
   cout<<"到頂點"<<g.GetValue(i)<<"的前一頂點為:"
       <<g.GetValue(path[i])<<endl;
 cin.get();cin.get();}
 PShortP1.cpp運行結(jié)果:
輸入圖的總邊數(shù):9
輸入9條有向有權(quán)邊的起點和終點序號及權(quán)值!
0 2 5 0 3 30 1 0 2 1 4 8 2 1 15
2 5 7 4 3 4 5 3 10 5 4 18
創(chuàng)建后的鄰接矩陣:
   0  99   5  30  99  99
   2   0  99  99   8  99
  99  15   0  99  99   7
  99  99  99   0  99  99
  99  99  99   4   0  99
  99  99  99  10  18   0
輸出鄰接矩陣相應(yīng)圖的每個頂點:
A(0,2,5) B(0,3,30) C(1,0,2) D(1,4,8) E(2,1,15) F(2,5,7)
從頂點A到其他各頂點的最短距離為:
到頂點A的最短距離為:0
到頂點B的最短距離為:20
到頂點C的最短距離為:5
到頂點D的最短距離為:22
到頂點E的最短距離為:28
到頂點F的最短距離為:12
從頂點A到其他各頂點的最短路徑的前一頂點為:
到頂點B的前一頂點為:C
到頂點C的前一頂點為:A
到頂點D的前一頂點為:F
到頂點E的前一頂點為:B
到頂點F的前一頂點為:C