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

中国地质大学（武汉） 数据结构 课程设计报告 指导老师: 朱晓莲 班级序号: 学 号: 姓 名: 实习二 求最短路径 一．问题描述 试设计一个算法，求图中一个源点到其他各顶点的最短路径。 二．基本要求 （1）用邻接表表示图； （2）按长度非递减次序打印输出最短路径的长度及相应路径。 三．测试数据 四.用到的数据结构和函数 （1）定义数组 typedef char VertexType; typedef int Adjmatrix; typedef struct { VertexType vexs[MVNum]; //顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，类型假定为int型 }MGraph; （2）迪杰斯特拉算法 void Dijkstra(MGraph *G,int v1,int n) { //用迪杰斯特拉算法求有向图G的v1顶点到其他顶点v的最短路径P[v]和其权D[v] //设G是有向图的邻接矩阵，若边i,j不存在，则G[i][j]=Maxint //S[v]为真当且仅当v在S中 int D2[MVNum],P2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v=n;v++) {//初始化S和D S[v]=FALSE; //设置最短路径终点集 D2[v]=G-arcs[v1][v]; //设置初始的最短路径值 if(D2[v]Maxint) P2[v]=v1; //v1是v的前驱 else P2[v]=0; //v无前驱 } D2[v1]=0; S[v1]=TURE; //S集初始时只有源点，源点到其自身的距离为0 //开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中 for(i=2;in;i++) { min=Maxint; for(w=1;w=n;w++) if(!S[w]D2[w]min) { //w顶点离v1顶点更近 v=w; min=D2[w]; } S[v]=TURE; for(w=1;w=n;w++) //更新当前最短路径及距离 if(!S[w](D2[v]+G-arcs[v][w]D2[w])) { //修改D2[w]和P2[w] D2[w]=D2[v]+G-arcs[v][w]; P2[w]=v; } } printf(路径长度 路径\n); for(i=1;i=n;i++) { printf(%5d,D2[i]); printf(%5d,i); v=P2[i]; while(v!=0) { printf(-%d,v); v=P2[v]; } 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;j=n;j++) { if(G-arcs[i][j]!=Maxint) P[i][j]=j; //j是i的后继 else P[i][j]=0; D[i][j]=G-arcs[i][j]; } for(k=1;k=n;k++) { //做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径P[i][j]上 for(i=1;i=n;i++) for(j=1;j=n;j++) { if(D[i][k]+D[k][j]D[i][j]) { D[i][j]=D[i][k]+D[k][j]; //修改长度 P[i][j]=P[i][k]; printf(dij=%d,pij=%d\n,D[i][j],P[i][j]); } } } } 六．源代码 #includestdio.h #includestdlib.h #define MVNum 100 //最大顶点数 #define Maxint 32767 enum boolean{ FALSE,TURE }; typedef char VertexType; typedef