设计一个地铁路线规划小工具

概述

最近在找房子，因为想找一个去几个地方都相对方便的位置，自己去地图上看还挺麻烦的，所以想做个小工具，本文就简单介绍一下实现过程。目前的功能还比较简单，主体方法就是根据一个输入的始发站，列出其他所有站点到这个地方的站数最少路线。



数据获取

从网上找了高德地图的接口数据: http://map.amap.com/service/subway?_1469083453978&srhdata=1100_drw_beijing.json . 对拿到的json串进行解析，其中包含每条地铁线路的信息，并依次列出线路上的每个站点。



通过解析数据，要得到的主要就是各个站点的信息，站点定义的数据结构如下:



private String id;



private String name;



private Set<String> lines = new HashSet<String>(); //所在线路



private String position;



private String pinyin;



private Set<String> nextStations = new HashSet<String>(); //相邻站点



所有站点汇总后可以看做一张图，nextStations字段就是用来表示边的信息。



路线规划

路线规划算法可以参考Dijkstra算法，由于现有的表现形式下，只是一个无向无权重的图，实现起来还要简单一些。



实现过程描述如下：



1. 新建两个map, knownPath和waitingPath，分别用来表示已经确定了最短路径的站点列表，和待处理的站点列表。初始化时，knownPath中只包含指定的起点，waitingPath中包含其他所有站点，并将距离设置成无穷大(用MAX = 20000表示)

2. 指定起点为当前节点

3. 依次处理当前的相邻节点，更新每个节点的最短距离

4. 从waitingPath中找到距离最短的节点，作为当前节点，重复第3步，并从waitingPath转移到knownPath

整个过程结束之后，会得到每个节点到起点的最短距离以及路线详情，然后可以根据这些数据计算路线详情的换乘情况。



对于换乘，主体判断逻辑是，如果一个站点的上一站和下一站所在路线不重合，就可以确定在这一站进行了换乘，比如灯市口-东四-朝阳门，灯市口在5号线上，朝阳门在2，6号线上，可以断定在东四肯定作了换乘。不过还有一些特殊情况要处理，比如说西直门到平安里，中间那站如果是车公庄（虽然现实中没人会这么干），实际就是作了换乘的，但是按刚才的逻辑就会判断成未换乘。



最终得到的路线信息中包含以下信息：



private String stationId;



private int length;



private int transferNum; //换乘数



private List<String> detail = new ArrayList<>(); //详细路径



用途

主体功能在上面已经完成，后边就可以根据需要再去自定义处理了。比如，加入我现在需要找到”距奥林匹克公园站15站以内且距天安门东站7站以内的位置”，就可以分别输入奥林匹克公园和天安门东，然后在结果中作相应的过滤，再取交集。



后续计划

目前做的还比较简单，只是简单考虑站数，但是实际上，不同站点的距离、耗时相差会比较大，再一个不同地方的换乘开销差别也很大。所以后续会试试能不能找到换乘站的详情数据，还有两站之间耗时的数据，并应用到算法中。



再一个是要找一个合适的方法做个界面出来，因为一直做的是纯后台，还没考虑清楚用什么合适。



其他的，还在考虑爬一下房价信息。



代码

https://github.com/lcy362/fox-subway

欢迎提意见。



原文地址: https://lichuanyang.top/posts/13793/