南昌航空大学数据结构与算法实验六

1、南昌航空大学实验报告课程名称：数据结构与算法实验名称：班级：XXX学生姓名：指导教师评定：XXX签名:一、实验目的实验六图的遍历XXX学号：XXXXXXXX图结构有着广泛的应用。二、实验内容本实验主要涉及两个方面的内容：一个是有关图的最短路径问题，用一个交通查询系统例子来验证迪杰斯特拉算法和费洛伊德算法；而另一个则工程项目实施过程中的关键路径问题 。三、程序分析设计一个交通查询系统， 能让游客查询从任一城市顶点到另一城市顶点之间的最短路径或最低花费或最少时间等问题。 对于不同查询要求， 可输入城市间的路程或所需时间或所需费用。本程序共分三个部分：（ 1）建立交通网络图的存储结构；（ 2）单源最

2、短路径；（ 3）实现两个城市顶点之间的最短路径。四、程序源代码该实例程序的源代码如下：（1）建立有向图的存储结构/ 文件名 CreateMGraph.cVoid CreateMGraph(MGraph * G，int n ，int e)/采用邻接矩阵表示法构造有向图G，n， e 表示图的当前顶点数和边数int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->vexsij=Maxint;/初始化邻接矩阵printf("输入 %d 条边的 i 、j 及 w

3、:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d,",&i,&j,&w);G->arcsij=w;printf("有向图的存储结构建立完毕n");/ 文件 dijkstra.cvoid Dijkstra(MGraph *G ,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;v<=nv+)Sv=FALSE;D2v=G->arcsv1v;if(D2v<Maxint)P

4、2v=v1;elsep2v=0;D2v1=0;Sv1=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+)if(!Sw&& D2w<min)v=w;min=D2w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw&& D2v+G->arcsvw<D2w)D2w=D2v+G->arcsvw;P2w=v;printf("路径长度路径 n");for(i=1;i<=n;i+)printf("%5d",D2i);printf(&q

5、uot;%5d",i);v=P2i;while(v!=0)printf("<-%d",v);v=P2v;printf("n");/ 文件 floyd.cvoid Floyd(MGraph *G,int n)int i,j,k,w;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(G->arcsij!=Maxint)Pij=j;elsePij=0;Dij=G->arcsij;for(k=1;k<=n;k+)for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(Di

6、k+Dkj<Dij)Dij=Dik+Dkj;Pij=Pik;/ 主程序#include#include#define MVNum100#define Maxint 32767enumbooleanFALSE,TRUE;typedef char VertexType;typedef intAdjmatrix;typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;#include "CreateMGraph

7、.c"#include "dijkstra.c"#include "floyd.c"void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);w, hile(xz!=0)printf("*求城市之间的最短路径*n");printf(&qu

8、ot;=n");printf("1.求一个城市到所有城市的最短路径n");printf("2.求任意的两个城市之间的最短路径n");printf("=n");printf("请选择：1、或2、选择0、退出： ");scanf("%d",&xz);if(xz=2)Floyd(G,n)printf("输入源点 (或称起点 ) 和终点 :v,w:");scanf("%d,%d",&v,&w);k=Pvw;if(k=0)print

9、f("顶点 %d 到 %d 无路径 !n",v,w);elseprintf("从顶点 %d 到%d 的最短路径是：%d!n",v,w,v);while(k!=w)printf("->%d",k);k=Pkw;printf("->%d",w);printf("路径长度 :%dn",Dvw);elseif(xz=1)printf("求单源路径，输入源点v:");scanf("%d",&v);Dijkstra(G,v,n);printf(&q

10、uot;结束求最短路径,再见 !n");五、实验结果输入图中顶点个数和边数n， e：7， 10 (表示输入7 个顶点和 10 条边 )输入 10 条边的 i、j 及 w1， 7，92， 1，202， 3，102， 4，303， 5，55， 4，125， 7，156， 5，86， 7，107， 3，18有向图的存储结构建立完毕*求城市之间的最短路径*=1求一个城市到所有城市的最短路径2求任意的两个城市之间的最短路径=请选择：1、或2、选择0、退出：1求单源路径，输入源点v:1 （表示求从顶点1 到其他所有顶点的最短路径）路径长度路径01/说明顶点 1 到 1路径长度为 0327672/说明顶点 1 到 2无路径， 32767 表示273<-7<-1/ 说明顶点 1 到 3 路径长度为 27，路径为 1，7， 3444<-5<-3<-7<-1325<-3<-7<