中国地质大学（武汉） 数据结构 课程设计报告 ****: *** 班级序号: 学 号: 姓 名: 实习二 求最短路径 一．问题描述 试设计一个算法，求图中一个源点到其他各顶点的最短路径
二．基本要求 （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;varcs[v1][v]; //设置初始的最短路径值 if(D2[v]
