这是一个创建于 3356 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近需要频繁出差，于是用 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 run2 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