根据校园各主要生活、学习、活动等场所、地点，设计并实现基于校园各场所之间的最短路径漫游。
要求：
(1).掌握数据结构的输入/输出；
(2).设计与实现校园各主要场所之间的最短路径算法；
(3).根据场所之间的最短路径及不同场所之间的路况信息，设置相应的步行、骑行等出行方式，计算到达每一目的地的时间及总的路程耗时；
(4).各主要场所、地点以及漫游状态，以地图缩、放方式动态展示；
(5).校园各主要场所、地点不少于50个。
具体分析：
(1).打开初始界面，选择起始点与终止点，实现最短路径查询、耗时估算功能。
(2).操作方式
在首页的选择界面中“起始位置”和“终点位置”的下拉框里的50余个校园场所，然后选择步行或骑行的出行方式，点击“出发！”按钮，会在界面右侧的地图上以动画方式展现出具体的最短路径，可以缩放地图查看，左侧将显示起始点与终止点的坐标，界面左下位置框内会显示距离与耗时。
(1).首先需要找到合适的地图资源，在这里我们选用的是OpenStreetMap。OpenStreetMap是一款由网络大众共同打造的免费开源、可编辑的地图服务。它是利用公众集体的力量和无偿的贡献来改善地图相关的地理数据。选中我们需要的地图，将其导出为OSM文件。利用文本格式打开.osm文件可以看到其中包含了很多信息，包括每一个结点的ID、经度纬度等等。由于.osm文件采用的是xml格式，利用Python的相关函数对数据进行分析处理，去除多余或者无效的数据并进行可视化。 (2).得到各个结点后需要设计寻找最短路径的算法并尽可能对其进行优化，同时需要完善对不同出行方式的描述，获得准确的出行路线。 (3).进行UI交互界面的设计。UI常用的一般有MFC和Qt,考虑到Qt的界面优美，有丰富的API函数，以及上手容易等优点，在这里我们选用Qt。 (4).后续的检查与调试。
Python算法，Qt交互界面设计，OSM文件解析
使用OpenStreetMap，手动设置框选边界范围，导出范围内的地图数据信息为.osm文件，地图上的各种要素均由若干个结点构成，每个结点拥有自己的id及属性，同时行车道路与人行道路的特征以不同的tag 进行区分。但是直接导出同时也会带来问题，在目标区域内会产生大量不需要的结点，在后续算法处理中需要进行剔除。
数据示例：
OSM文件成功导出后，编写程序将其进行解析，首先构建结点数据结构class node，定义结点所需要的属性如结点id，能否行车，连接其他结点情况，间距，经纬度，上一步的结点等信息。
编写OSM数据解析算法，首先通过使用结点的经纬度信息，结合地球半径进行结点间距离的计算，如果我们假设地球是一个完美的球体，那么它的半径就是地球的平均半径，记为r。
如果以0度经线为基准，那么根据地球表面任意两点的经纬度就可以计算出这两点间的地表距离（这里忽略地球表面地形对计算带来的误差，仅仅是理论上的估算值）。使用的公式是Haversine公式，半正矢公式(haversine equation)用于计算两经纬度点的距离，公式为：
其中lat是纬度，lon是经度；lat2 - lat1为两点纬度之差，lon2-lon1为两点经度之差；r=6378.137（KM）为地球半径。
利用bisect库，使用二分法查找结点在list中的位置：
判断确定距离当时位置最近的结点，从而为后续的计算做好准备：
判断道路类型，通过结点tag进行区分，若为'footway', 'track', 'path', 'living_street', 'pedestrian'则使用type1表示仅步行，若为'tertiary', 'residential', 'service', 'primary', 'secondary'使用type2表示人车均可通行：
编写算法连接两个结点，其中两点间距距离由上述部分计算，同时去除没有道路连接的单独无意义的结点：
导入道路与建筑数据，首先通过筛选取tag为“way”类型的结点，再通过highway，building，进行区分。
当tag为highway时直接导入此结点相关信息：
当tag为building时，为了便于后续的距离计算，我们将使用最近的结点来代替此建筑物，所以先要得到最近的结点，再将最近结点的信息导入：
导入地图边框数据，筛选tag为bounds的结点进行导入：
检查坐标是否在学校内部，将坐标与上述导入的边界进行比较来确定：
导入OSM文件中的内容：
Dijkstra算法是典型的单源最短路径算法，用于计算一个结点到其他所有结点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
迪杰斯特拉算法最朴素的思想就是按长度递增的顺序产生最短路径。即每次对所有可见点的路径长度进行排序后，选择一条最短的路径，通过有限次的操作得到的最终结果就是对应顶点到源点的最短路径。需要注意的是，该算法处理的一般是有向图，而在生活中的路线肯定是双向的，所以就需要对数据结构做一定的处理。
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
算法的具体实现：
这里用书上的例子对我们采用的算法进行一个解释
V0是源点，V5是终点。一开始V0指向V5,V4,V2，在第一个结点中存下的V0的ID，后继结点（V5,V4,V2）的地址，走到当前结点的距离，在后续的结点中还需要加上前结点的地址信息，为了方便描述过程，现列表如下：
| 结点 | Present | Next | Rest | Prior | Dist | Predist | Way |
|---|---|---|---|---|---|---|---|
| 1 | *V0 | [*V5,*V4,*V2] | NULL | NULL | [10,30,100] | [] | (V0->V2) |
| 2 | *V2 | [*V3] | *V5,*V4 | *V0 | [30+20,10+50] | [10,30,100] | (V0->V4->V3) |
| 3 | *V3 | [*V5] | *V5,*V4 | *V4 | [50+10,30+60,100] | [50,60] | (V0->V4->V3->V5) |
在存储结构的选择上，我们选择用Python中的类，实例化成一个个结点来存储地图中的信息，各个结点之间相互连接形成图。图（Graph）结构是一种比树结构更为复杂非线性的数据结构，在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行等等都可以抽象成图结构。不同于书上采用邻接矩阵来存储信息，在这里由于地图本身是由很多的结点构成，一条看上去不算长的路可能包含了几百甚至几千个结点，如果仍然采用邻接矩阵来存储，将会占据大量的空间。对于结点类，它的数据成员主要由当前结点的ID、经纬度等直接从OSM文件得到的一些数据和前后结点的地址信息以及经过加工处理的相关的距离构成。存储结点的地址以及书上的三个一维数组的存储我们采用了列表的形式，Python的列表非常的灵活，不论是添加新的元素还是查找删除替换操作，都可以很轻松的做到。
folium是js上著名的地理信息可视化库leaflet.js为Python提供的接口，通过它，我们可以通过在Python端编写代码操纵数据，来调用leaflet的相关功能，基于内建的osm或自行获取的osm资源和地图原件进行地理信息内容的可视化，以及制作优美的可交互地图。
首先，在MapShower这个类中进行地图初始化map_init，用folium.Map创建一张地图并进行相应设置，比如指定中心坐标，设置地图缩放尺寸，以及控制绘图调用的地图样式等等。
当鼠标在地图上移动时实时在右上角的位置上显示经纬度信息，并且将定义好的MousePosition部件用add_to()添加到先前创建的地图Map上。
用MiniMap创建一个自定义缩放范围的小地图添加到MAP中，将导入的数据赋给building_info和building_name，并用save()函数将其保存为html文件用于在后续UI界面中的显示。
**
定义一个函数update_path_building(self, building_name1, building_name2, trans_type) 更新建筑间最短路径，将选择起始点与终止点的名称，经纬度坐标信息存入bd1_和bd2_，然后通过判断trans_type是“步行”还是“骑行”的方式规划不同的路线，速度，距离。
并且将路径描绘出来，且可以用tooltip设置在路径上显示该路线是用什么出行方式从某起始点到达终止点的。
最后用folium.Marker()将起始点与终止点在地图上做个标记点，最终将添加部件后的地图存为school_map.html，且该函数返回该路径的距离与耗时时间。
定义一个初始化函数进行相应的初始化。
首先使用designer初步设计界面要素，主要包括提示语文本框，起点、终点位置、出行方式的选择下拉列表，确定按钮以及显示距离、耗时的结果，并预留地图显示的位置，设置背景颜色、字体字号等，效果如下：
保存为MainWindow.ui文件，并使用cmd执行‘pyuic5 -o MainWindow.py MainWindow.ui’命令生成Python代码。
导入地图并初始化：
将地图中解析的地点导入到起始点位置的下拉列表，将起始地点设在伟长楼，目的地点设在吾馨楼。
将已选择的起始地点以及目的地地点位置对应的经纬度导入对应的文本框位置并显示在界面中。
当点击“出发”按钮时，根据选取的起始点、目的地点以及出行方式调用计算距离和耗时的函数，并将结果传入对应的文本框。
在生成的python代码中创建程序入口。
界面效果大致如下：
运行MainWindow.py弹出导航界面，上方显示导航系统提示语，用户可以在左侧下拉框选择起始点、终止点位置以及出行方式。当用户选择位置时，其坐标的经纬度可以同步显示；当用户点击“出发”按钮时，左下方会显示本次路线的距离以及预计耗时；右侧同时显示动态路径规划，且可以用鼠标进行缩放、拖拽；用户选择步行时路径显示为蓝色，选择骑行时路径显示为红色。地图左下角可显示当前的比例尺，右下角为校园整体缩略图。选择步行后点击出发，效果如下图所示：
切换成骑行后效果图如下：
进行局部缩放所展示的效果如下（鼠标停留在路线上时会显示当前路径起点、终点以及出行方式）：
经过多次测试，本系统可以根据起始点、终止点及出行方式的不同进行合理的路径规划并在地图中显示，界面流畅无明显卡顿，且符合实际情况，较好地满足题目要求。
(1). 地图网络构建：
最初得到题目的时候对于地图路径的获取毫无思路。校园内道路交错纵横难以标注节点信息，手动标注的结果必然不尽人意。最初我们考虑采用mesh化的校园地图，以网格结构为基础实现路径规划，但在估计工作量后发现并非想象的那么简单。随后通过大量的资料查询，我们发现了网上的开源地图数据OpenStreetMap，从其中导出的道路信息正是我们所需要的节点与连接结构构成的地图网络。最终我们以对map.osm的解析为基础构造了路径规划所需要的地图网络。
(2). 路径规划算法选择：
根据文献资料的查询，我们总结了常见的与多用于商用地图的最短路径规划算法。其中包括Floyd算法，Dijkstra算法，A*算法及其改良版本。其中Floyd算法实现方便，但由于其算法的时间复杂度O(
(1). 使用邻接表替代稀疏邻接矩阵用于存储结点与边信息，提高存储效率，优化储存空间。使用优先队列优化边查找速度，最优边检索时间复杂度从O(n)降至O(logn)。以此为基础采用经堆优化的Dijkstra算法，时间复杂度相较于传统Dijkstra算法O(n^2)降为O(nlogn)。
(2). 图的构建采用来自OpenStreetMap的地图数据而非手动选取校园内结点，使地图网络结构具有高精度，为合理的路径规划提供基础。
(3). 借助基于leaflet.js开发的folium包实现地图可交互动态可视化，实现校园漫游功能。