Loading... > 原文链接：[https://www.zhihu.com/question/34899146/answer/3527453988](https://www.zhihu.com/question/34899146/answer/3527453988) 结论： 先举例子：五条线，四次换乘，比如 15 -> 13 -> 10 -> 房山 -> 燕房。 其他：2、15、11、S1、燕房、亦庄 T1，从中选择两个，看一下它们两个到 10 号线经过的那条线是否相交，不相交的话即满足条件。 --- **分析过程**：因为 10 号环线和大多数地铁直接相连，也就是说，两个和 10 号线相连的地铁，只需要 X -> 10 -> Y 就可以到达。观察和 10 号线不相连的地铁： 2：内环环线。2 -> 很多 -> 10 15：右上角紫色的那个：15 -> 昌平/8/5/13/14 -> 10 11：左边中间那个竖着的不知道怎么形容的颜色（肤色？）：11 -> 6 -> 10 S1：11 左边的棕色的：S1 -> 6/1 -> 10 燕房：左下角橘黄色，[阎村](https://www.zhihu.com/search?q=%E9%98%8E%E6%9D%91&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A3527453988%7D)东以西的部分：燕房 -> 房山 -> 10 亦庄T1：最下面的红色的：T1 -> 亦庄 -> 10 **发现他们都可以通过一次换乘到达 10 号线** 综上所述，任意选择两个验证一下到达 10 号线的中转线路不相交，都可以达到 X -> X' -> 10 -> Y' -> Y 的效果，即四次换乘。  百度地图 --- 找 AI 写了一下代码，数据采用的 [https://**github.com/ZhuwenJ/subw**ay/blob/master/src/data/subway.txt](https://link.zhihu.com/?target=https%3A//github.com/ZhuwenJ/subway/blob/master/src/data/subway.txt) ，不过代码或者数据似乎有问题。 代码跑出来的是 15号线 -> 5号线 -> 1号线 -> 9号线 -> 房山线 -> 燕房线，共 6 线 5 换乘。 但是从地图上看，四次换乘就够了 1. 15 和环线 10 号没有相邻，需要有一个（5/8/13/14/昌平中转），15 -> X -> 10 2. 10 号和上面中转以及房山相连，可以 10 -> 房山 3. 房山 -> 燕房 即 15 -> X -> 10 -> 房山 -> 燕房，总共 4 次。对照数据查看，地铁数据没有房山线的首经贸。因此绕了一下  --- 占个坑。聊天提到这个，然后搜索“**北京地铁任意两点的最小换乘方案中，换乘次数最多的是哪个**”，第一条就是这个提问 有时间了代码写一下试试\~  --- 目前想法是，将每个地铁压缩成一个点，不同地铁有换乘的话，对应的点建立一个 w=1 的[无向边](https://www.zhihu.com/search?q=%E6%97%A0%E5%90%91%E8%BE%B9&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A3527453988%7D)。最终形成一个联通的[无向图](https://www.zhihu.com/search?q=%E6%97%A0%E5%90%91%E5%9B%BE&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A3527453988%7D)。 然后整体计算一个[多源最短路](https://www.zhihu.com/search?q=%E5%A4%9A%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A3527453988%7D)（Floyd）。取最大值应该就是了 最后修改：2024 年 07 月 21 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏