pshortpm.txt

数据结构的c++实现,源代码全部在C++builder中运行.第六部分

//最短路径(狄克斯特拉算法)PshortP.h
//从一个顶点到其余各顶点的最短路径
void PShortPath(AdjMatrix &G,int v0,int dist[],int path[])
//网G从下标v0到其他顶点的最短距离dist和最短路径下标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;//标记顶点v0已从集合T加入到集合S中
 //在当前还未找到最短路径的顶点集中选取具有最短距离的顶点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];
    }
  //当已不再存在路径时算法结束;此语句对非连通图是必需的
  if(mindis==MaxValue) return;
  s[u]=1;//标记顶点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经顶点u到其他顶点的最短距离和最短路径
    dist[j]=dist[u]+G.GetWeight(u,j);
    path[j]=u;
   }
 }
}
//狄克斯特拉算法PshortPM.cpp
#include<iostream.h>
#include<iomanip.h>
#include "graph0.cpp"
#include "PshortP.h"
//狄克斯特拉算法测试
void main()
{cout<<"PShortPM.cpp运行结果:\n";
 int n=6,e=9,k2=1;
 RCW rcw[]={{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}};
 AdjMatrix g(n,k2);
 g.Creatgraph(n,e,rcw);
 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();}
 PShortPM.cpp运行结果:
从顶点A到其他各顶点的最短距离为:
到顶点A的最短距离为:0
到顶点B的最短距离为:20
到顶点C的最短距离为:5
到顶点D的最短距离为:22
到顶点E的最短距离为:28
到顶点F的最短距离为:12
从顶点A到其他各顶点的最短路径的前一顶点为:
到顶点B的前一顶点为:C
到顶点C的前一顶点为:A
到顶点D的前一顶点为:F
到顶点E的前一顶点为:B
到顶点F的前一顶点为:C