《交通咨询系统设计》由会员分享，可在线阅读，更多相关《交通咨询系统设计（11页珍藏版）》请在金锄头文库上搜索。
1、 目录1 概述 .1 1.1 课程设计名称.1 1.2 课程设计目的.1 2 系统分析.2 2.1 问题描述.2 2.2 设计要求.2 2.3 课程设计内容.2 3 概要设计.2 3.1 定义相关的数据类型.2 3.2 总体结构图 .2 图5.1.3 3.3 模块调用图 .3 图5.2.3 4 详细设计.3 4.1建立一个有向图的存储结构 .3 4.2 迪杰斯特拉算法.3 4.3 费洛伊德算法.3 4.4 主函数流程图.4 5运行与测试.6 实例的运行数据 .6 图5.4.6 5.1 有向图的存储结构建立 .6 5.2 单源最短路径.7 5.3 任意一对顶点间最短路径.7 6 总结与心得.8
2、7 参考文献.8 8 附录（程序源代码）.81 概述概述1.1 课课程程设计设计名称名称交通咨询系统设计（最短路径问题）1.2 课课程程设计设计目的目的充分了解并掌握最短路径问题及其应用，根据有向图的存储结构解决实际问题。 2 系系统统分析分析2.1 问题问题描述描述对于该设计，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶 点表示城市，边表示城市之间的交通关系。这个交通系统可以回答2.2 设计设计要求要求1、建立交通网络的存储结构2、提供一个城市到任意城市最短路径查询功能 3、提供任意两个城市间最短路径查询功能 4、提供程序测试算法 5、界面友好2.3 课课程程设计
3、设计内容内容设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或 最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花 费。3 概要概要设计设计3.1 定定义义相关的数据相关的数据类类型型采用邻接矩阵定义图： typedef struct VertexType vexsMVNum;/顶点数组、类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵、假定为int型 MGraph; 建立图的存储结构 #include #include#define MVNum 100/最大顶点数 #define Maxint
4、32767 enum booleanFALSE,TRUE;typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum;/顶点数组、类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵、假定为int型 MGraph; /MGraph是以邻接矩阵存储的图类型 3.2 总总体体结结构构图图图5.13.3 模模块调块调用用图图交通咨询管理系统建立 有向 图的 存储 结构单源 路径 查询 问题任意 一对 顶点 间最 短路 径主函数 main创建有向图 void MGr
5、aph打印系统 菜单调用费洛伊德算 法void Floyd调用迪杰斯特算 法void dijkstra图5.24 详细设计详细设计4.1建立一个有向建立一个有向图图的的存存储结储结构构有向图的邻接矩阵是不对称的，实现其算法，我们只需要输入有向图的有向边及权值即可。采 用邻接矩阵表示法构造有向图G，输入图中顶点个数和边数，初始化邻接矩阵，紧跟着系统提 示输入边及权值，则系统提示有向图的存储结构建立完毕。4.2 迪杰斯特拉算法迪杰斯特拉算法为了解决单源路径问题，我们提出了迪杰斯特拉算法，它主要是按路径长度递增产生顶点的 最短路径算法，其实现如下： 初始化S和D，置空最短路径终点集，置初始的最短路径
6、值；Sv1=TRUE;Dv1=0;/S集初始时只有源点，源点到源点的距离为0；While(S集中顶点数 #include #define MVNum 100 /最大顶点数 #define Maxint 32767 enum boolean FALSE,TRUE ; typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型 MGraph; int D1MVNum,P1MVN
7、um; int DMVNumMVNum,PMVNumMVNum; void CreateMGraph(MGraph *G,int n,int e) /采用邻接矩阵表示法构造有向图G，n,e表示图的当前顶点数和边数 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;iarcsij=Maxint; /初始化邻接矩阵printf(“输入%d条边的i,j以及w:n“,e); for(k=1;karcsij=w; printf(“有向图的存储结构建立完毕!n“); void Dijkstra(MGraph *G,int v1,int n) /用Dijkstra算法
8、求有向图G的v1顶点到其他顶点v的最短路径Pv及其权Dv/设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint/Sv为真当且仅当v属于s,即已求得从v1到v得最短路径 int D2MVNum,P2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;varcsv1v; /置初始的最短路径值 if(D2varcsvwarcsvw; P2w=v; printf(“路径长度 路径n“); for(i=1;iarcsij!=Maxint) Pij=j;else Pij=0; Dij=G-arcsij; for(k=1;k%d“,k); k=Pkw; printf(“-%d“,w); printf(“路径长度: %dn“,Dvw); else if(xz=1) printf(“求单源路径,输入源点v:“); scanf(“%d“, Dijkstra(G,v,n); printf(“结束求最短路径,再见!n“);
