来源：http://t.cn/EbMSlGi

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

现在的公共交通越来越方便，很多城市都有地铁，日常使用的地图 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 号线可有你走的了。

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