求最短路径_C语言程序.doc

中国地质大学（武汉）数据结构课程设计报告指导老师: 朱晓莲 班级序号: 学 号: 姓 名: 实习二 求最短路径一问题描述 试设计一个算法，求图中一个源点到其他各顶点的最短路径。二基本要求 （1）用邻接表表示图； （2）按长度非递减次序打印输出最短路径的长度及相应路径。三测试数据 四.用到的数据结构和函数（1）定义数组typedef char VertexType;typedef int Adjmatrix;typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，类型假定为int型MGraph;（2）迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n) /用迪杰斯特拉算法求有向图G的v1顶点到其他顶点v的最短路径Pv和其权Dv/设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint /Sv为真当且仅当v在S中int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; /设置初始的最短路径值if(D2vMaxint)P2v=v1; /v1是v的前驱else P2v=0; /v无前驱D2v1=0;Sv1=TURE; /S集初始时只有源点，源点到其自身的距离为0/开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin) /w顶点离v1顶点更近v=w;min=D2w;Sv=TURE;for(w=1;warcsvwarcsvw;P2w=v;printf(路径长度 路径n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=P2i;while(v!=0)printf(-%d,v);v=P2v;printf(n);（3）费洛伊德算法void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+) /设置路径长度D和路径path初值for(j=1;jarcsij!=Maxint)Pij=j; /j是i的后继elsePij=0;Dij=G-arcsij;for(k=1;k=n;k+) /做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij)Dij=Dik+Dkj; /修改长度Pij=Pik;printf(dij=%d,pij=%dn,Dij,Pij);六源代码#includestdio.h#includestdlib.h#define MVNum 100 /最大顶点数#define Maxint 32767enum boolean FALSE,TURE ;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，类型假定为int型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;/*建立有向图的存储结构*/void CreateMGraph(MGraph *G,int n,int e) /采用邻接矩阵表示法构造有向图G,n和e表示图的顶点数和边数int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint; /初始化邻接矩阵printf(输入%d条边的i,j及w：n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完成。n);/*迪杰斯特拉算法*/void Dijkstra(MGraph *G,int v1,int n) /用迪杰斯特拉算法求有向图G的v1顶点到其他顶点v的最短路径Pv和其权Dv/设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint /Sv为真当且仅当v在S中int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; /设置初始的最短路径值if(D2vMaxint)P2v=v1; /v1是v的前驱else P2v=0; /v无前驱D2v1=0;Sv1=TURE; /S集初始时只有源点，源点到其自身的距离为0/开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin) /w顶点离v1顶点更近v=w;min=D2w;Sv=TURE;for(w=1;warcsvwarcsvw;P2w=v;printf(路径长度 路径n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=P2i;while(v!=0)printf(-%d,v);v=P2v;printf(n);/*费洛伊德算法*/void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+) /设置路径长度D和路径path初值for(j=1;jarcsij!=Maxint)Pij=j; /j是i的后继elsePij=0;Dij=G-arcsij;for(k=1;k=n;k+) /做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+Dkj%d,k);k=Pkw;printf(-%d,w);printf(路径长度为:%dn,Dvw);else if(xz=1)printf(求单源路径，输入源点v:);scanf(%d,&v);Dijkstra(G,v,n);printf(结束求最短路径。n);七测试情况1.测试第一个无边图2.测试第二个有向图测试均满足题目条件。八收获通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对迪杰斯特拉算法和费