造了一个查找地铁换乘的轮子

[jasonlee]

最近需要频繁出差，于是用 Python 和 JavaScript 造了一个寻找最短路径的工具，托管在 https://metro.lihanming.me/。界面看起来像这样：

它具有以下的功能：

1. 站点提示（输入站名、线路名，可以提示一些车站）
2. 根据当前位置寻找最近的车站，并提示怎么走过去（感谢高德地图）
3. 寻找路径（支持按最短时间、换乘较少等模式查询）
4. 提示行车时间（目前京沪穗三个地方支持实际时间，其他城市支持估算时间）

目前支持中国内地所有有地铁的城市、香港（不含轻铁和电车）、台北和东京（两大地铁和 JR 部分线路）。伦敦正在写。线路保存在 JSON 文件中，可以随时扩展。

比较有趣的细节：

1. 支持虚拟换乘。虚拟换乘站会提示，并且会有不需要虚拟换乘的方案提供。（南京西路、上海火车站）
2. 支持不同运营商或票务系统。如果行程需要转乘会提示。（如龙阳路、三元桥、青衣等）

目前几个需要努力的地方：

1. 优化变量名。尽可能做到没有文档也能看懂；
2. 连续多个换乘站的处理（四惠-四惠东、中环-金钟等）；
3. 提升算法性能。目前使用的算法在初始化时需要的时间比较长；
4. 多语言支持。目前都是使用本地文字；
5. 用户界面优化。城市太多了需要想个办法呈现；
6. 几个城市合在一起做一个大的系统，并且包括一些城际线路（珠三角、长三角）
7. 其它（包括你们的意见和建议）；

最后欢迎大家试试，希望它能在你们旅行出差的时候帮到你们，也欢迎你们提出意见和建议。

网址： https://metro.lihanming.me/

源码： https://github.com/DaZui/MetroSearch/

Jason

[zhen14]

没有 iOS ？

[jasonlee]

@zhen14 iOS 我觉得直接浏览器放到桌面比较方便。

[sobigfish]

json 里没有发现里程 2 站间距离很重要吧（大概）-。-

[jasonlee]

@sobigfish 不是用里程，而是用时间。因为不知道换乘需要多少里程。而且快车哪怕多走一点，时间也比慢车短。不过里程对算票价很有用。

[jasonlee]

话说有什么新的城市需要添加么？比如北美和欧洲

[zjqzxc]

查北京地铁的时候经常只出现一种路径，例如西直门到东直门只出现了二号线方案；五路居到五道口只出现了换成 10 号线方案；
北京地铁换成很多幺蛾子， 4/9 换成有同站台换成， 2->1 下了楼梯就是，但 1->2 要绕一大圈。。

不过话说这种公共交通工具查询这些地图软件已经很成熟了。。

[jasonlee]

@zjqzxc 西直门到东直门…莫非 13 号？其实这就是选路问题。
同站台和人流管制确实很麻烦，但我也没有精力去一个个收集这种细节。
这东西就是自己给自己开发的轮子，就图一个简单快捷而已。很多应用都做得更好。

[franklinyu]

@jasonlee {{15L}}:我感覺你其實可以給每個「站點對」保存前 K 的路徑（ K 是你自己決定的常數），然後專門分出一個後臺進程計算。畢竟每個「站點對」只需要計算一次，工作量對於服務器來說應該不算大。當用戶請求到還沒計算好的站點對的時候，將這個「站點對」從計算序列中提取出來，放到序列的前面，同時給用戶返回一個「計算中……」的回覆。

[franklinyu]

@jasonlee {{15L}}:或者可以看一下這個 StackOverflow 問題： http://stackoverflow.com/q/4971850

[jasonlee]

@franklinyu 一般来讲找多条路径用的是 BFS 。但 BFS 的复杂度很高。我正在考虑的思路是一路存储，就是在 BFS 的时候顺手存储所有沿路的站点。 Dijkstra 是单点出发所有点，也是一种可行的思路。

[franklinyu]

@jasonlee {{30L}}:如何用 BFS 來找多條路徑？

[jasonlee]

@franklinyu BFS 的演算法是這樣的，從起點出發往終點遍曆，只要能到終點的都算一條路徑，如果是死路則返回。最困難的地方在於，有的時候由於圖過分複雜，很難及時返回。（我個人測試，廣州、深圳和香港可以用 BFS ，上海、北京就無法及時返回結果）。這裡有一篇文章，可供聊作參考。 http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

[franklinyu]

@jasonlee {{32L}}:所以你的圖裡沒有權重的？如果有權重的話廣度優先搜索並不能保證最短路徑先返回誒。

[jasonlee]

@franklinyu 有權重。可以退化為無權重算，然後逐一計算路徑所需的時間，在瀏覽器用 JavaScript 解決。我看了一下 BFS 失敗的原因是內存溢出，畢竟這是 BFS 的老問題。

[jasonlee]

@franklinyu 這個排序的問題實際上是個大問題。比起客戶端運算排序，用一個直接尋找最短路徑的算法會更快一些，也更節約服務器內存。

[franklinyu]

@jasonlee 內存溢出？一個城市也就幾十個站，而且地鐵圖是稀疏圖，怎麼會這麼耗內存？是 JavaScript 垃圾回收太遲？

[franklinyu]

我在 CS.StackExchange 裡面幫你問了一下，好像最好的方法也只是逐對計算了： http://cs.stackexchange.com/q/62383

[jasonlee]

@franklinyu 北京上海東京個個都是數百個站。如果帶權重就不是稀疏圖了(因為不為 0)。這是個極為頭疼的問題。我一開始廣州深圳都是可以 BFS ，在做上海的時候發現的這個問題才轉向 Floyd 。 BFS 應對大規模圖的方法主要是剪枝，但怎麼剪是個問題。

[jasonlee]

@franklinyu 事實上幾個更坑的問題是有一部分單向運行的(北京機場線)，此時馬上變成有向圖。為了壓縮矩陣我毅然廢了這個功能。

[akaayy]

百度地图。