1 问题内容与目的要求

1.1 算法产生的背景：

Floyd 算法又称为加点法、插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特 · 弗洛伊德命名。它与 Dijkstra 算法类似，但Dijkstra 算法是基于贪心算法的思想。

1.2 题目内容：

基本要求：

针对XX大学YY校区，设计一个校园导游图系统，为来访的客人提供信息查询服务。要求：

1.在老师提供的“校园景点.txt”文件中，存储了YY校区的景点信息，信息分为两部分 ，二者用一个空行隔开。其中第一部分的每一行，以“编号>名称>简介”的格式描述了一个景点的信息，“>”起到将不同信息分隔开的作用；第二部分的每一行，以“编号>编号>距离”的格式描述两个景点之间路径的长度，例如0>1>200表示编号为0的景点与编号为1的景点之间的路径长度为200米，“>”还是起到分隔作用。

2.依据“校园景点.txt”提供的信息，将校园景点及景点之间的路径抽象为一个带权无向图，以图中顶点表示景点编号，以边的权值表示两个景点之间路径之长度，在实验报告上绘制这个带权无向图

3.编写程序实现以下功能：

（1）程序读取“校园景点.txt”，依所读取的数据创建上述带权无向图的存储结构，要求存储结构表示了各景点的信息（编号、名称、简介），还表示了景点之间的路径长度。

（2）程序在屏幕上按下述格式，显示所有景点的编号、名称、简介等。

（3）通过景点编号，可检索并显示该景点的全部信息

（4）通过景点名称，可检索并显示该景点的全部信息

（5）为来访客人提供查询任意两个景点之间的一条最短路径，其结果按“1>4>5>8=160”格式显示，表示从1号到8号景点的最短路径依次经过了编号为1、4、5、8的景点，路径长度为160米。

更高要求：

（6）提供校园平面图的编辑功能：增、删景点；增、删道路，修改已有信息等

（7）提供校园导游图的仿真界面—即将上面的第2点，路径的发布与走向尽量画得接近真实情况，并显示到屏幕上。

1.3 要实现的目的：

基本：针对XX大学YY校区，设计一个校园导游图系统，为来访的客人提供信息查询服务。更高：在基本的校园导游系统上，（1）除了给管理员提供查询的服务，再增加上增删改的服务；（2）大致提供校园导游图的仿真界面。

2 总体思路与工程结构

2.1 系统功能模块

根据功能分析，系统功能模块图如图1所示：

2.2 项目结构

2.2.1 工程总体结构

建立名为“2020_校园导游系统”的工程，整个实验将在其中进行。该小工程包括头文件headPro.h,文件body1.cpp,文件main.cpp。如图2所示：

2.2.2 函数之间的调用关系

补充：由于小工程的函数多，画出会很丑陋，这里使用图3的方式的呈现，圆圈的数字与2.2.3函数及功能里的函数的编号，即函数（编号）一一对应。

2.2.3 函数及功能

3 主要数据结构、关键问题和算法

3.1 数据结构

表1：校园景点表

将校园平面图抽象为图4所示的带权无向图：

其中：顶点编号与“表1：校园景点表”中景点编号一一对应，代表相应景点；边上的权值代表两个景点之间的路径长度（单位：米）

数据结构的设计——邻接矩阵：

需要存储的信息有两个方面。一是校园景点表各景点的描述信息；二是各景点之间的联系，即各景点之间的路径信息。为此，一是用一维数组存储校园景点表的信息；二是二维数组表示各景点之间的联系。通过两个数组之间下标的对应关系，使得两方面的信息发生关联。

思考：接下来执行 MGraph G; 命令，系统会如何给G分配空间，试着画出其示意图，试着把以下两方面信息存储进去：需要存储的信息有两个方面，一是校园景点表各景点的描述信息；二是各景点之间的联系，即各景点之间的路径信息。

3.2 关键问题

3.2.1 求导游图的任意两个景点的最短路径

（1）那什么是求导游图的任意两个景点的最短路径呢？

答：简言之，就是在导游图已有的景点（顶点）、道路（边），找连接两个景点的最短道路，得到最短道路的长度值（边的权值）、最短道路的经过的景点次序，即从开端景点到中间景点（可能没有，即直达），再到终端景点的次序。

（2）那怎么求导游图的任意两个景点的最短路径呢？

答：

1、通常使用Floyd算法求导游图的任意两个景点的最短路径；大体的关键步骤如下：

1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w （一般称为中间点）使得从 u 到 w 再到 v 比已知的路径更短。如果是，更新它（专业术语为：松弛）。

3）遍历直到结束，这时候存储图的数据结构就得到了多源最短路径。

2、中间涉及两个比较关键数组：

1）二维数组dist[][]是用于存储图的景点之间的最短路径的邻接矩阵，比如dist[i][j] = 150;表示从编号为i的景点到编号为j的景点的最短路径的长度值为150米;比如dist[i][j] = INFINITY (32767)表示从编号为i的景点到编号为j的景点之间没有连通路径，也就是无法直接到达和间接到达。

2）二维数组path[][] 是记录图的最短路径的中间景点次序的矩阵，比如path[m][n] = -1;表示从编号为m的景点到编号为n 的景点是直达的，即没有中间景点；比如path[m][n] = 6; 表示从编号为m的景点到编号为n 的景点是间接到达的，即含有编号为6中间景点（可能还有其它中间景点）

3.3主要算法说明

3.3.1 Floyd算法

Floyd 算法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法不是那么难且有效，关键的部分是对三道循环的理解。代码大致如下：

//三道循环实现

优点：难度系数不高，可以算出任意两个节点之间的最短距离，代码编写不难。

缺点：时间复杂度比较高，不适合计算大量数据。时间复杂度 O（n^3）,空间复杂度 O（n^2）。

3.3.2 递归算法

那什么是递归算法呢？

答：递归算法是一种直接或者间接调用自身函数或者方法的算法。（俗话就说成“自己调用自己”）递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。

本小工程主要使用递归算法辅助输出显示两个景点的最短路径，使用于printPath ()函数里面。

4 测试

5 总结

5.1 任务完成情况

5.1.1 已经完成的任务

（1）程序读取“校园景点.txt”，依所读取的数据创建带权无向图的存储结构，要求存储结构表示了各景点的信息（编号、名称、简介），还表示了景点之间的路径长度。

（2）程序在屏幕上按下述格式，显示所有景点的编号、名称、简介等。

（3）通过景点编号，可检索并显示该景点的全部信息。

（4）通过景点名称，可检索并显示该景点的全部信息。

（5）为来访客人提供查询任意两个景点之间的一条最短路径，其结果按“1>4>5>8=160”格式显示，表示从1号到8号景点的最短路径依次经过了编号为1、4、5、8的景点，路径长度为160米。

（6）提供校园平面图的编辑功能：增、删景点；增、删道路，修改已有信息等。

（7）提供校园导游图的仿真界面—即将上面的第2点，路径的发布与走向尽量画得接近真实情况，并大致显示到屏幕上，但不牙雅观。

5.1.2尚未完成的任务

无

5.2不足与改进信息

不足之处主要表现在：

1）程序的交互性差，可改进为提供菜单选项，使得每个选项代表用不同的算法来进行搜索；

2）程序运行效率不高，可适当修改算法，进行优化；

3）图的景点之间关系，即图的邻接矩阵空间是有限的、静态定义（可能导致无法增加新的景点），且没有扩容的操作，建议可以使用动态定义或增加扩容操作

4）程序中只知道函数调用涉及栈、new操作涉及堆，了解还是不足，建议可更多地了解底层；

5）程序中对指针和引用的使用不熟，建议更多地了解相关、解析更多更易吸收的书籍或文档。

5.3 自评与诚信声明

自评：XX分

该数据结构课程设计的参考文献资料如后面所列。保证除了参考这些文献资料和与同学讨论之外，没有抄袭某同学的、某文献的，否则甘愿接受记0分的处罚。

附录一 实验环境

Windows 10 + CodeBlocks

附录二 用户手册

1）在Windows环境下，“校园景点.txt”文件跟.exe文件要放在同一目录，就可以直接打开.exe文件或者利用CodeBlocks编译器打开，这里有打开.exe文件的图片

2）然后双击.exe文件就行，然后会看到导游系统的服务菜单，如图

然后键盘输入英文字母y(yes)进入服务，服务时多看菜单，多参考我那实验测试过程，多使用服务编号2进行全局看景点。当你不要服务时，就输入服务编号0，再按回车键，再按任意键退出校园导游系统。

附录三 校园景点.txt文件

附录四 源代码

头文件headPro.h如下:

文件body1.cpp如下:

文件main.cpp如下：