使用python实现后端功能,由于地铁图需要进行展示,svg图需要花费比较多的时间,这里使用了 MetroFlow 库构建的地铁地图编辑器,可以在画布上构建矢量图,
实现站点路线的创建。
用法:
打包好后完整目录:
window下执行:双击"一键启动.bat",启动成功后会自动打开浏览器。
文件目录:
结果:
1.地铁数据的获取
对地铁线路进行建模,首先要获取地铁站点数据。
利用高德地图平台获取,打开高德地图后,选择地铁视图,页面上便会显示国内各个城市的地铁线路图。
在Chrome浏览器中用F12打开开发者视图后,再切换到广州地铁选项卡,获取http请求。
https://map.amap.com/service/subway?_1706940819067&srhdata=4401_drw_guangzhou.json
清洗数据,获取站点名称、站点路线、经纬度保存到excel里面。通过方式可以方便快捷的获取地铁的站点数据
2.构建图模型
在获取到了地铁站点图后,则可以对数据进行构建图模型。构建图模型的方式可以有邻接矩阵和邻接表。考虑到复杂的网络结构图,使用NetworkX
来进行图的构建,
由于地铁是可以无向的,所以要构建无向图。NetworkX这里是使用邻接链表的方式创建,每个节点都有一个关联的链表,链表中存储了与该节点直接相连的其他节点。
这种表示方法在实际使用中更为常见,并且适用于稀疏图,因为它可以节省大量的空间,只存储存在连接的节点,而不需要额外的空间来表示不存在的连接。
,根据经纬度,把两个站点之间的距离一并构建在图模型里面。有了图模型后,就可以利用相应的算法来规划路径了
3.最优路径算法 基于Dijkstra 算法求最优路径
用于计算图中节点之间的最短路径,从起始节点开始,逐步扩展到达其他节点的最短路径。在每一步中,选择当前距离起始节点最近的节点,
然后更新与该节点相邻的节点的距离值。通过不断重复这个过程,直到到达目标节点或者遍历完所有节点,就可以得到起始节点到所有其他节点的最短路径
某些情况下,可能存在多条路径具有相同的最短长度,所以这里的最短路径是返回一个列表。
4.所有路径 深度优先搜索(DFS)算法
获取图中两个节点之间的所有简单路径,其中简单路径是指不经过重复节点的路径。底层原理是使用深度优先搜索(DFS)算法。
深度优先搜索是一种图遍历算法,其基本思想是从起始节点开始,尽可能深地探索每个分支,直到无法再继续前进,
然后回溯到上一个节点,继续探索其他分支,直到遍历完整个图或者找到目标节点为止。
深度优先搜索被用来从起始节点开始,逐步探索图中的每条路径,直到达到目标节点或者无法再继续前进为止。这样就可以获取到两个节点之间的所有简单路径。
这里考虑到实际生活中和可行性,使用DFS算法对路径长度做了一定的限制,获取最优路径的长度,根据长度来调整设定DFS算法的深度,以便快速获取所有可行的所有路径。
5.优化查询速度
项目中用到小型数据库,用于记录查询过的路径,站点名称等等。
优化:完整线路规划
完整线路规划 ,以上算法只实现了具体的地铁站点间的规划,如果起始点是任意地点而不是地铁站,那么需要找出距离最近的地铁站。
通过高德api求出起始点的经纬度,然后遍历地铁站,找出最近的地铁站,从而使用上面的算法找最优线路规划。
带权路径规划,可以设定带权参数,可实现带权路径规划,比如:根据时间、距离、费用等参数进行路径规划。
换乘时间规划,可以设定换乘参数,实现换乘时间规划
源码部署本地运行:
后端:切换到 program.py 所在目录 执行
pip install -r requirements.txt
运行 python program.py
前端:
执行安装包命令
npm install
部署:
npm install build
执行后有dist文件,下载一个tomcat,把对应文件dist、index.html、data.json放到webapps/ROOT里面后到/bin里面点击startup.bat启动前端。