校园导游咨询(最短路径)

数据结构课程设计 实验报告 学 号： 姓 名： 提交日期： 成 绩： 东北大学秦皇岛分校 网络技术 实验报告 东北大学秦皇岛分校电子信息系 第1页 设计题目：校园导游咨询 一、实验目的 （1）熟练掌握图的创建及遍历基本操作算法。 （2）熟练掌握最短路径算法。 （3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。 二、需求分析 实验内容 【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】 (1) 设计你所在学校的校园平面图,所含景点不少于10 个。以图中顶点表示校内各景点,存放景点名称、代 号、简介等信息;以边表示路径,存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。 【测试数据】 由读者根据实际情况指定。 【实现提示】 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。 【实现功能】 这个系统给用户提供查询景点，浏览路径，寻找最佳的方案到达目的地，还提供了最佳路径。 三、概要设计 1.系统分析： 用的图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索 ，查找所需 的路径。再用迪 杰 特 斯 拉 算法求出 一个景点到其 他 景点之间的最佳路径。然后再用弗 洛 伊 德算法求出 要查询的出 发 点到目的地的最短路径。 网络技术 实验报告 东北大学秦皇岛分校电子信息系 第2页 2．功能模块图； 3.各个模块详细的功能描述 （1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息。 （2）浏览校园全景（Brow ser）：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出。 开始 定义变量 浏览校园全景 查看各景点游览路线 选择出发点和目的地 显示此图的邻接矩阵 退出系统 Void Menu()进入菜单 Sw itch()选择功能 查看景点信息 结束 网络技术 实验报告 东北大学秦皇岛分校电子信息系 第3页 （3）查看各景点游览路线（ShortestPath_DIJ）：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上。 （4）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点...