1、 摘要 摘要 本次课程设计主要核心为利用迪杰斯特拉算法实现无向图的最短路径的计 算和求解。要求理解迪杰斯特拉算法的具体实现流程、学会正确使用该算法求解 实际问题。本次课程设计具体内容是：为自己学校建立一个校园导航系统。该系 统应该具有：查询任意两点最短路径以及查询任意一点到其他各点的最短路径。 本程序要求结合最短路径迪杰斯特拉算法以及相应的数据结构的定义和使 用，实现一个最短路径算法的简单应用。本文主要包括的函数模块有：数据结构 定义、无向图的建立、导航图建立、最短路径求解及主函数模块。还有运行调试 过程的截图，最后附上程序清单，以供查阅。 本课程设计是对书本知识的简单应用， 以此培养大家用书
2、本知识解决实际问 题的能力；培养实际工作所需要的动手能力；培养以科学理论和工程上能力的技 术，规范地开发大型、复杂、高质量的应用软件和系统软件。 关键字：校园导航，迪杰斯特拉算法，最短路径，算法设计，数据结构 目录 目 录 摘要摘要 I 1 1 问题描述问题描述 .1 2 2 方案设计方案设计 .2 2.12.1 数据结构定义模块数据结构定义模块. 2 2.22.2 功能模块定义功能模块定义 2 2.2.1 无向图构造模块 .2 2.2.2 导航图建立模块 .2 2.2.3 求最短路径模块 .3 2.2.4 主菜单 3 3 3 流程图流程图4 3.13.1 系统运行流程图系统运行流程图 . 4
3、 3.23.2 迪杰斯特拉算法流程图迪杰斯特拉算法流程图 . 5 4 4 功能模块代码实现功能模块代码实现.6 4.14.1 创建无向图函数创建无向图函数 . 6 4.24.2 导航菜单生成导航菜单生成 . 7 4.34.3 最短路径求解函数最短路径求解函数 8 5 5 运行调试运行调试 11 5.15.1 查询系统导航界面查询系统导航界面 11 5.25.2 两点最短距离导航两点最短距离导航 11 5.35.3 某点到其他所有点最短距离某点到其他所有点最短距离. 12 5.45.4 退出系统退出系统 12 6 6 程序设计总结程序设计总结 . 13 7 7 参考文献参考文献 . 14 附录附
4、录 程序清单程序清单 . 15 1 问题描述 1 问题描述 这是一个最短路径算法的简单应用，体现了理论与实际的结合。在完成本系 统过程中，应用所学知识解决具体的实际问题。 根据本设计要求，首先应该根据本学校的具体实际，建立校园平面图。然后 根据该图建立无向图的邻接矩阵，矩阵的值表示两点之间的实际距离。最后根据 用户请求调用迪杰斯特拉算法，并输出相应的路径信息。 该系统还应该设计可视化导航键面，方便用户使用。根据本课程设计要求， 本系统应该具备如下功能： 1、查询任意两点间的最短路径（包括途经地点以及最短距离） ； 2、查询任意一点到其他各点的最短路径（包括途经地点以及最短距离） ； 3、能完成
5、连续的查询工作； 4、用户查询完后能方便的退出程序系统。 2 方案设计 2 方案设计 2.1 数据结构定义模块 本模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储 结构 1来真实反映各节点到其他所有节点的路径长度（权值大小） 。 其数据结构定义为： typedef struct char* vexsMAX_V; /顶点向量 int arcsMAX_VMAX_V;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧数 MGraph; 2.2 功能模块定义 2.2.1 无向图构造模块 根据实际情况设计学校平面图（至少包含 10 个地点） ，并采用邻接矩阵实现 对该平
6、面图节点及权值信息的存储 3。包括：各定点的名称（地点名） ，各个节 点到其他所有节点的真实路径长度（赋权值） 4。即对无向图两点间的边值赋值。 本课程设计中涉及地点编号及信息如下： (1) 南门 (2) 行政楼 (3) 学生会堂 (4) C 区 (5) 静明湖 (6) 图书馆 (7) 分析测试中心 (8) 第二教学楼 (9) 羽毛球场 (10) 励志楼 (11) 学生公寓中心 (12) 食堂区 (13) 医务室 (14) 凌云楼 (15) 篮球场 (16) 生化楼 (17) 东门 (18) 文德楼 (19) 排球场 (20) 第一教学楼 (21) 学生活动中心 (22) 足球场 (23) 北门 (24) 西苑 (25) 学生洗
