阅读全文

⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 https://miketech.it/metro-transfer-plan/ 「Mike.Zhou」欢迎转载，保留摘要，谢谢！

• 数据获取
• 图的二维数组展现
• Dijkstra
• 代码的实现
• 优化
• 尾巴

---

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
4. 新的源码解析文章实时收到通知。每周更新一篇左右。
5. 认真的源码交流微信群。

---

现在的公共交通越来越方便，很多城市都有地铁，日常使用的地图App都提供了地铁线路换乘方案的功能，只要输入起点和重点，App就能给出你换乘的方案，可是这个功能背后的算法又是怎么样的呢。这篇文章将会告诉你。

说到最短路径算法不外乎就是那么几种，广度优先深度优先Dijkstra之类的，这篇博客将会讲述Dijkstra算法，其他的最短路径算法我的其他文章也自己讨论过，在这里不过多说了。写这篇文章主要是因为我看其他的关于讲Dijkstra算法的博客都停留在算法阶段，代码可以用，但是实用价值不多，那么这篇文章会直接带你来实现一个上海地铁换乘规划算法。

数据获取

文章中的所有代码都上传到了GitHub，代码中有一个MetroRequester模块会自动连接上海地铁的官网（http://www.shmetro.com/）来下载所有的站点信息。request_shanghai_metro_data()函数会返回一个StationManager和一个LineManager对象。

StationManager实例是用来获取站点信息的，存放着上海地铁的344个站点和每个站点的地铁线路，比如 人民广场 站有 1，2，8 号地铁线。

LineManager对象存放的的是地铁线路和站点之间的关系，也就是说每条线路有什么站是存在这个对象中的。这个对象提供了一个计算两个直达站点最短需要的站数的函数，比如莘庄到徐家汇，函数会计算出来最短路径为7站，因为可以坐1号线直达，但是不能计算出非直达站点的最短站数，比如莘庄到静安寺，这两站需要乘坐1号线并且换乘其他线路才能到达。

对于单次的路径，我抽象了一个Route类，他的实例储存着起始站，终点站，乘坐的线路，和站数，比如下图对应的实例：代表从徐家汇乘坐1号线经过5站到达人民广场。

图的二维数组展现

那么基础的数据结构已经设计好了，那么现在来开始讲算法吧，首先我们先把问题简化一下吧。暂时只讨论，徐家汇，陕西南路，汉中路，曲阜路四站，用到的地铁线路只有1号线（红色）和12号线（绿色）。

处理路径问题的时候用到的数据结构为图（Graph），那么我们来画出这个图，四个站分别为四个节点，边长代表两个节点之间的站的个数。

下图中左侧就是表达出来的图，可以看到徐家汇是没有办法直答曲阜路的（徐家汇只有1号线，9号线，11号线2；而曲阜路只有8号线和12号线），必须通过换乘地铁才可以。

并且，边长代表到达另一个节点的最短距离，也就是最少需要的站的个数，在这四个站中，陕西南路到达汉中路有两个直达方案：

• 直接乘坐12号线经过南京西路到达汉中路
• 直接乘坐1号线经过黄陂南路，人民广场新闸路到达汉中路

我直接忽略了第二个方案，因为第二个方案不会有人去乘坐的，因为12号线只要坐两站就到而1号线要做4站。

通过左边的图，我们可以使用一个二维数组来表示其中的关系，右边的表可以表示，行代表起始站，列代表终点站。比如第一排第三列代表徐家汇到汉中路要经历7站，第一排第四列代表徐家汇到曲阜路并没有直达方案，所以是一个无限符号，这张表一般被成为临街矩阵，在程序中可以抽象为一个二维数组，我将他称为v_matrix

Dijkstra

Dijkstra是一个最短路径算法，他的核心就是边的松弛

举一个例子，现在我要计算出来徐家汇到曲阜路的最短路径，那么首先我们要算出徐家汇到所有地方的最短路径。那么首先把表格的第一列拿出来代表徐家汇为起点。在程序中第一列可以抽象为一个1维数组，我将他命名为dis数组，代表distance。

首先找到离徐家汇最近的一个顶点，是陕西南路，那么徐家汇到陕西南路最短距离为3就已经确认，因为陕西南路是离徐家汇最近的一个顶点，所以两点之间不可能存在一个比这3站还近的中专线路，毕竟两点之间线段最短。

然后接下来就是汉中路顶点。我们不妨先看看陕西南路顶点都有哪些边通向别的顶点，陕西南路可以通往汉中路和徐家汇，呢么有没有一种方案能够通过陕西南路来缩短徐家汇直达汉中路的7站距离呢？

通过观察邻接矩阵v_matrix，有的，从徐家汇到陕西南路，再从陕西南路到汉中路只需要走5站，要优于徐家汇直达汉中路的7站，在代码层面这是在比较 dis[2] 与dis[1] + v_matrix[1][2]的大小

我们发现， dis[2] = 7 , 大于 dis[1] + v_matrix[1][2] = 5于是我们更新dis[2]为5，于是徐家汇到汉中路的最短距离确认为5, 这个过程称之为边的松弛。

同理，我们可以通过判断 dis[2] + v_matrix[2][3] = 6 ，小与代表曲阜路的dis[3] = 无穷大。将曲阜路的路径缩短为6.

至此所徐家汇顶点到其余各顶点的最短路径就求出来了。

更详细一点的讲解可以看这篇文章:

https://www.cnblogs.com/GnibChen/p/8875247.html

代码的实现

上面就是基本的算法，可是如果dis数组和v_matrix邻接矩阵中只有一个整数代表最短距离的话，这段代码还是没什么用的，我想知道徐家汇到曲阜路怎么走，如果像上面那样编程的话程序只会告诉我最短距离为6站，没有任何用途。

所以为了实现能够让程序记住换乘的路径，我抽象出了一开始提到的Route对象，代表一个直达的路径，在v_matrix数组中的每一个元素都是一个Route对象实例，当可以直达的时候，这个实例的stops为最短的站数，当不可以直达的时候stops为9999代表无限大。

并且dis数组也不是只保存了松弛过后边的长度，而是保存了一个键值对，key为最短边的长度，value为一个数组，储存着若干个Route实例，遍历这个数组即可得到所有的换乘方案。比如下图的结构代表从徐家汇到上海科技馆的换乘方案，要经历10站，先做11号线到江苏路，再从江苏路换乘2号线到上海科技馆。

其余的代码直接在Github上看，不做多余的讲解了。

优化

上面其实就是Dijkstra的核心了，不过，要是凭着上面的讲解真的能够写出足够优秀的地铁换乘规划算法吗？

答案是否定的，上面讲解到通过松弛将徐家汇到汉中路的站数缩短到了5站，代价是换乘一次，本来徐家汇是可以乘坐1号线直达汉中路的，只是多了两站而已，但是我们的算法却偏偏选择了换乘。在真实生活中，我是不会去为了少两站换乘的，毕竟换乘还要等下一班地铁还要走很多路，陕西南路1号线换乘10号线或者12号线可有你走的了。

同样再试一下莘庄到汉中路，这两个站是可以通过一号线直达的。跑一下程序：

可以看到算法并没有给出一号线直达的方案，而是选择了换乘两次，所以这样算出来的方案非常不切实际，归根究底，我们没有考虑到换乘的巨大代价。

所以我引入了一个偏执值bias来表示换乘的代价，我将他设置为3，代表换乘一次和坐三站花费的时间等价。

回到徐家汇到汉中路的问题，在上文我是这么写的：

dis[2] = 7 , 大于 dis[1] + v_matrix[1][2] = 5于是我们更新dis[2]为5

这次计算我们引入bias为3

dis[2] = 7 ； dis[1] + v_matrix[1][2] + bias = 8, 可以看到在比较的时候引入一个bias值导致这次计算出来直达的7站是一个最优方案，因为换乘的边长由5变成了8。

通过这个右滑，来再看看莘庄到汉中路的方案：

这一次算法给出了合理的最优方案。

当然这样可能也不太完美，因为对于顶点之间的边长，我仅仅是使用了站点数来表示，如果用真实距离来表示会更加精准，或者用不同的站到不同的站的经历时间来表示长短也是不错的选择。

尾巴

那么换乘算法已经有了，你有没有想过地图App是怎么确定你周围最近的地铁站的呢？没有想法的同学可以看我几年前写过的博客：周围的餐馆有哪些？GeoHash算法

这个项目的Github地址: https://github.com/Yigang0622/Metro-Transfer-Algorithm