这是一个创建于 3040 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近需要频繁出差，于是用 Python 和 JavaScript 造了一个寻找最短路径的工具，托管在 https://metro.lihanming.me/。界面看起来像这样：
它具有以下的功能：
- 站点提示（输入站名、线路名，可以提示一些车站）
- 根据当前位置寻找最近的车站，并提示怎么走过去（感谢高德地图）
- 寻找路径（支持按最短时间、换乘较少等模式查询）
- 提示行车时间（目前京沪穗三个地方支持实际时间，其他城市支持估算时间）
目前支持中国内地所有有地铁的城市、香港（不含轻铁和电车）、台北和东京（两大地铁和 JR 部分线路）。伦敦正在写。线路保存在 JSON 文件中，可以随时扩展。
比较有趣的细节：
- 支持虚拟换乘。虚拟换乘站会提示，并且会有不需要虚拟换乘的方案提供。（南京西路、上海火车站）
- 支持不同运营商或票务系统。如果行程需要转乘会提示。（如龙阳路、三元桥、青衣等）
目前几个需要努力的地方：
- 优化变量名。尽可能做到没有文档也能看懂；
- 连续多个换乘站的处理（四惠-四惠东、中环-金钟等）；
- 提升算法性能。目前使用的算法在初始化时需要的时间比较长；
- 多语言支持。目前都是使用本地文字；
- 用户界面优化。城市太多了需要想个办法呈现；
- 几个城市合在一起做一个大的系统，并且包括一些城际线路（珠三角、长三角）
- 其它（包括你们的意见和建议）；
最后欢迎大家试试，希望它能在你们旅行出差的时候帮到你们，也欢迎你们提出意见和建议。
网址： https://metro.lihanming.me/
源码： https://github.com/DaZui/MetroSearch/
Jason
 |
1
niboy 2016-08-03 19:37:29 +08:00
提个问题吧，比如在上海的金海路到世纪大道，其实有 2 种路线，实际搜出来的只有一种
|
 |
2
SourceMan 2016-08-03 19:39:00 +08:00 via iPhone
最优路径的算法思路大概怎么样的？
|
 |
3
moult 2016-08-03 19:51:14 +08:00
杭州的，江陵路到客运中心，虽然 1 号线直达，但是换成一下 4 号线，就算加上换成时间，也比直达的快。
|
|
7
niboy 2016-08-03 21:12:49 +08:00
@jasonlee
1. 12 号线金海路--》到大连路换 4 号线 --》世纪大道，起点站，胜在一路有座 2. 12 号线金海路--》到巨峰路换 6 号线--》世纪大道，比路线 1 少一站，但站内换乘走路时间长，而且不一定有座 可以和百度地图、腾讯地图等的路线对比一下 |
 |
8
jasonlee OP @niboy 我看了一下。估计是因为大连路那里需要过黄浦江，列车运行时间长一些。 Floyd 算法的主要缺点就是你找不到第二长的线路。我看看广度优先搜索能不能找到。谢了啊。
|
|
9
jasonlee OP @moult 我新增了一个“换乘多”的模式，将换乘时间缩短为 2 分钟。主要是我不知道各个地方的列车间隔。如果列车衔接妥当，那么换乘所花的时间就短。
|
|
10
niboy 2016-08-03 22:49:10 +08:00
我下载了 Android 客户端，看起来就是网站，请问 lz 是用什么封装成 APK 的？难道就是一个 webview 加载了 bootstrap 的网站？
|
|
11
jasonlee OP @niboy 正解。我写了一个 webView 。专门为 Android 写客户端的原因是因为一部分 Android 浏览器获取的地理位置不正确，所以无奈之下封装了。如果你是用 Chrome 等可以添加到桌面的浏览器，那我觉得不用下客户端也没事。
|
 |
12
wdlth 2016-08-03 23:31:26 +08:00
我认为如果只有一个结果的话就不要写换乘多了……
|
 |
14
franklinyu 2016-08-04 01:10:39 +08:00
@jasonlee 弗洛伊德算法是不是可以一次性找到所有「站點對」的最短路徑？而不用在收到請求的時候實時計算？
|
|
15
jasonlee OP @franklinyu 是的，這就是原因。但 Floyd 這個演算法不能找到第二長的路徑，十分頭疼。
|
 |
16
kenshin 2016-08-04 10:54:59 +08:00
挺棒的想法，前阵子去上海正好有这样的需求，当时的想法是自己有时间撸一个，没想到已经有成品了。
提个建议： 之前在上海的时候，想去迪士尼，出发地点附近有两个地铁线：老西门站与小南门站；通过地图 APP ，告诉我老西门站距离较慢 /较远，建议小南门站；结果发现，小南门的确时间或许比较少，但是需要换乘 n 站，结果这个 APP 就没有计算出每个换乘站需要走多久，需要等下趟车多久。 所以，能否再加入一些人工干预，比如： - 各个换乘站步行时间 - 每趟车的间隔时间 - 从出发点到地铁站的时间 |
 |
17
lgh 2016-08-04 12:23:32 +08:00
|
|
18
jasonlee OP @kenshin 不显示换乘时间的考虑就是这个。这个程序的好处就是简单。如果要显示这么细的话，就变成地图了(笑)。列车间隔也很难搞，因为不同时候的间隔不同。不过多个首站确实值得考虑，我设计一下流程来。
|
 |
21
zhen14 2016-08-04 17:25:55 +08:00
没有 iOS ？
|
 |
23
sobigfish 2016-08-04 23:34:28 +08:00
json 里没有发现里程 2 站间距离很重要吧（大概）-。-
|
|
24
jasonlee OP @sobigfish 不是用里程，而是用时间。因为不知道换乘需要多少里程。而且快车哪怕多走一点，时间也比慢车短。不过里程对算票价很有用。
|
|
25
jasonlee OP 话说有什么新的城市需要添加么？比如北美和欧洲
|
 |
26
zjqzxc 2016-08-05 11:42:18 +08:00
查北京地铁的时候经常只出现一种路径，例如西直门到东直门只出现了二号线方案；五路居到五道口只出现了换成 10 号线方案；
北京地铁换成很多幺蛾子， 4/9 换成有同站台换成， 2->1 下了楼梯就是，但 1->2 要绕一大圈。。 不过话说这种公共交通工具查询这些地图软件已经很成熟了。。 |
|
27
jasonlee OP @zjqzxc 西直门到东直门…莫非 13 号？其实这就是选路问题。
同站台和人流管制确实很麻烦，但我也没有精力去一个个收集这种细节。 这东西就是自己给自己开发的轮子，就图一个简单快捷而已。很多应用都做得更好。 |
|
28
franklinyu 2016-08-08 02:45:31 +08:00
@jasonlee {{15L}}:我感覺你其實可以給每個「站點對」保存前 K 的路徑（ K 是你自己決定的常數），然後專門分出一個後臺進程計算。畢竟每個「站點對」只需要計算一次，工作量對於服務器來說應該不算大。當用戶請求到還沒計算好的站點對的時候，將這個「站點對」從計算序列中提取出來，放到序列的前面，同時給用戶返回一個「計算中……」的回覆。
|
|
29
franklinyu 2016-08-08 02:52:47 +08:00
@jasonlee {{15L}}:或者可以看一下這個 StackOverflow 問題： http://stackoverflow.com/q/4971850
|
|
30
jasonlee OP @franklinyu 一般来讲找多条路径用的是 BFS 。但 BFS 的复杂度很高。我正在考虑的思路是一路存储，就是在 BFS 的时候顺手存储所有沿路的站点。 Dijkstra 是单点出发所有点，也是一种可行的思路。
|
|
31
franklinyu 2016-08-08 10:25:27 +08:00
@jasonlee {{30L}}:如何用 BFS 來找多條路徑？
|
|
32
jasonlee OP @franklinyu BFS 的演算法是這樣的，從起點出發往終點遍曆，只要能到終點的都算一條路徑，如果是死路則返回。最困難的地方在於，有的時候由於圖過分複雜，很難及時返回。（我個人測試，廣州、深圳和香港可以用 BFS ，上海、北京就無法及時返回結果）。這裡有一篇文章，可供聊作參考。 http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
|
|
33
franklinyu 2016-08-08 13:25:45 +08:00
@jasonlee {{32L}}:所以你的圖裡沒有權重的？如果有權重的話廣度優先搜索並不能保證最短路徑先返回誒。
|
|
34
jasonlee OP @franklinyu 有權重。可以退化為無權重算，然後逐一計算路徑所需的時間，在瀏覽器用 JavaScript 解決。我看了一下 BFS 失敗的原因是內存溢出，畢竟這是 BFS 的老問題。
|
|
35
jasonlee OP @franklinyu 這個排序的問題實際上是個大問題。比起客戶端運算排序，用一個直接尋找最短路徑的算法會更快一些，也更節約服務器內存。
|
|
36
franklinyu 2016-08-09 00:57:47 +08:00
@jasonlee 內存溢出？一個城市也就幾十個站，而且地鐵圖是稀疏圖，怎麼會這麼耗內存？是 JavaScript 垃圾回收太遲？
|
|
37
franklinyu 2016-08-09 01:14:19 +08:00
我在 CS.StackExchange 裡面幫你問了一下，好像最好的方法也只是逐對計算了： http://cs.stackexchange.com/q/62383
|
|
38
jasonlee OP @franklinyu 北京上海東京個個都是數百個站。如果帶權重就不是稀疏圖了(因為不為 0)。這是個極為頭疼的問題。我一開始廣州深圳都是可以 BFS ，在做上海的時候發現的這個問題才轉向 Floyd 。 BFS 應對大規模圖的方法主要是剪枝，但怎麼剪是個問題。
|
|
39
jasonlee OP @franklinyu 事實上幾個更坑的問題是有一部分單向運行的(北京機場線)，此時馬上變成有向圖。為了壓縮矩陣我毅然廢了這個功能。
|
 |
40
akaayy 2016-08-10 21:58:53 +08:00 via Android
百度地图。
|
|
41
jasonlee OP @akaayy 这是个轮子。另外百度地图目前无法提示出站换乘和转乘。这方面做得比较好的其实是日本人。
|
 |
42
wshcdr 2016-08-11 14:57:24 +08:00
以前写过类似的，这东西其实不容易写的...
|
 |
43
jojobobo 2016-08-11 21:01:52 +08:00
非常帮,,哈哈 为什么你这么棒
|
 |
46
kyzylsy 2016-08-17 17:48:35 +08:00
web 版点击寻找线路根本没有反应。。。差评
|
Select Language