算法与数据结构课程设计《兰州道路交通网络信息查询源程序》.docx

《算法与数据结构课程设计《兰州道路交通网络信息查询源程序》.docx》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计《兰州道路交通网络信息查询源程序》.docx（8页珍藏版）》请在第一文库网上搜索。

1、兰州道路交通网络信息查询ttinc1udettinc1udeWdefineMVNumIOo最大顶点数WdefineMaxint32767enumboo1eanFA1SE,TRUE)；typedefcharVertexType;typedefintAdjmatrix；typedefstructVertexTypevexsMVNum；顶点数组，类型假定为char型AdjmatrixarcsMVNumMVNum；邻接矩阵，假定为int型MGraph;voidCreateMGraph(MGraph*G,intn,inte)采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数intarcsEM

2、VNumMVNum；inti,j,k,w;for(i=1；ivexsEi=(char)i；.for(i=1；i=n;i+)for(j=1;jarcsij=MaXint；初始化邻接矩阵printf(,rshuru%dtiaobiandei,j,w：nr,e)；for(k=1；k=e；k+)读入e条边，建立邻接矩阵scanf(,r%d,%d,%d&i,&j,&w)；G-arcsij=w;)printf(,ryouxiangtudecunchujiegoujianIiwanbi!nn);)voidDijkstra(MGraph*G,intv1,intn)用Dijkstra算法求有向图G的V1顶点到其

3、他顶点V的最短路径Pv及其权Dv设G是有向图的邻接矩阵，若边i,j不存在，则Gij=MaxintSv为真当且仅当vS,即已求得从V1到V的最短路径intD2MVNum,P2MVNum；intV,i,w,min;enumboo1eanSMVNum；for(v=1；varcsv1v；置初始的最短路径值if(D2vMaxint)P2v=v1/V1是V的前趋(双亲)e1seP2Ev=O;/V无前趋)D2v1=0；Sv1TRUE；/S集初始时只有源点，源点到源点的距离为0开始循环，每次求得V1到某个V顶点的最短路径，并加V到S集中for(i=2;i;i+)其余-1个顶点min=Maxint;for(w=

4、1；w=;w+)if(!SEw&D2Ewmin)v=w；min=D2Ew1)w顶点离v1顶点更近Sv=TRUE;for(w=1；warcsvwarcsvw；P2w=v；/End_if/End_forprintf(,1ujingchangduIujingn)；for(i=1;i=n;i+)printf(%5d,r,D2i);printf(%5d,r,i)；v=P2i；whi1e(v!=0)printf(,r-%d,r,v)；v=P2v；)printf(,nn)；)voidF1oyd(MGraph*G,intn)intDEMVNumEMVNum,PEMVNumMVNum；inti,j,k,v,w;

5、for(i=1；i=n;i+)设置路径长度D和路径path初值for(j=1;jarcsiEj!=Maxint)Pij=j;j是i的后继e1sePijO;Dij=G-arcsij；)for(k=1；k=n；k+)for(i=1；i=n；i+)做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pijfor(j=1;j=n;j+)if(Dik+Dkj%dn,k)；输出后继顶点k=Pkw；继续找下一个后继顶点)printf(ff-%dff,w)/输出终点Wprintf(,Iujingchangdu：%dn,f,DvEw)；)e1seif(xz=1)printf(,qiudanyuanIujing,shuruqidianv：)；scanf(,%d,r,&v)；Dijkstra(G,v,n);调用迪杰斯特拉算法printf(,rjieshuqiuzuiduanIujing,bybye!n,r)；