求最短路径_c语言程序

《求最短路径_c语言程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国地质大学（武汉）数据结构课程设计报告指导老师:朱晓莲班级序号:学号:姓名:实习二求最短路径一．问题描述试设计一个算法，求图中一个源点到其他各顶点的最短路径。二．基本要求（1）用邻接表表示图；（2）按长度非递减次序打印输出最短路径的长度及相应路径。三．测试数据四.用到的数据结构和函数（1）定义数组typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum]

2、[MVNum];//邻接矩阵，类型假定为int型}MGraph;（2）迪杰斯特拉算法voidDijkstra(MGraph*G,intv1,intn){//用迪杰斯特拉算法求有向图G的v1顶点到其他顶点v的最短路径P[v]和其权D[v]//设G是有向图的邻接矩阵，若边不存在，则G[i][j]=Maxint//S[v]为真当且仅当v在S中intD2[MVNum],P2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){//初始化S和DS[v]=FALS

3、E;//设置最短路径终点集D2[v]=G->arcs[v1][v];//设置初始的最短路径值if(D2[v]

4、;}S[v]=TURE;for(w=1;w<=n;w++)//更新当前最短路径及距离if(!S[w]&&(D2[v]+G->arcs[v][w]arcs[v][w];P2[w]=v;}}printf("路径长度路径");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("");}

5、}（3）费洛伊德算法voidFloyd(MGraph*G,intn){inti,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的后继elseP[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

6、;j<=n;j++){if(D[i][k]+D[k][j]

7、ntAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵，类型假定为int型}MGraph;intD1[MVNum],P1[MVNum];intD[MVNum][MVNum],P[MVNum][MVNum];/*建立有向图的存储结构*/voidCreateMGraph(MGraph*G,intn,inte){//采用邻接矩阵表示法构造有向图G,n和e表示图的顶点数和边数inti,j,k

8、,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=Maxint;//初始化邻接矩阵printf("输入%d条边的i,j及w：",e);for(k=1;k<=e;k