交通咨询系统设计

目录 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 7 参考文献 .8 8 附 录 （程序源代 码） .8 1 概述 1.1 课程设计名称 交通咨询系统设计（最短路径问题） 1.2 课程设计目的 充分了解并掌握最短路径问题及其应用，根据有向 图的存 储结构解决实际问题。 2 系统 分析 2.1 问题描述 对于该设计，可用一个图结构来表示交通网 络系统，利用 计 算机建立一个交通咨询系统。图中顶 点表示城市，边表示城市之间 的交通关系。 这个交通系统可以回答 2.2 设计要求 1、建立交通网络的存储结构 2、提供一个城市到任意城市最短路径查询功能 3、提供任意两个城市间最短路径 查询功能 4、提供程序测试算法 5、界面友好 2.3 课程设计内容 设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或 最低花费或最少时间等问题。对于不同的咨询要求、可 输入城市 间的路程或所需时间或所需花 费。 3 概要 设计 3.1 定义相关的数据类型 采用邻接矩阵定义图： typedef struct VertexType vexsMVNum;/顶点数组、 类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵、 假定为int 型 MGraph; 建立 图的存储结构 #include #include #define MVNum 100/最大顶点数 #define Maxint 32767 enum booleanFALSE,TRUE; typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum;/顶点数组、 类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵、 假定为int 型 MGraph; /MGraph是以邻接矩阵存储的图类型 3.2 总体结构图 图5.1 3.3 模块调用图 交通咨询管理系统 建立 有向 图的 存储 结构 单源 路径 查询 问题 任意 一对 顶点 间最 短路 径 主函数 main 创建有向图 void MGraph 打印系统 菜单 调用费洛伊德算 法void Floyd 调用迪杰斯特算 法void dijkstra 图5.2 4 详细设计 4.1建立一个有向图的存储结 构 有向图的邻接矩阵是不对称的，实现其算法，我们只需要输入有向图的有向边及权值即可。采 用邻接矩阵表示法构造有向图G ，输入图中顶点个数和边数，初始化邻接矩阵，紧跟着系统提 示输入边及权值，则系统提示有向图的存储结构建立完毕。 4.2 迪杰斯特拉算法 为了解决单源路径问题，我们提出了迪杰斯特拉算法，它主要是按路径长度递增产生顶点的 最短路径算法，其实现如下： 初始化S和D，置空最短路径终点集，置初始的最短路径值； 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,P1MVNum; 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 算法求有向 图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; print