中国地质大学（武汉） 数据结构 课程设计报告 ****: *** 班级序号: 学 号: 姓 名: 实习二 求最短路径 一．问题描述 试设计一个算法，求图中一个源点到其他各顶点的最短路径。 二．基本要求 （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 是有向图的邻接矩阵，若边不存在，则 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]arcs[v][w]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 的最短路...
