算法:在限制火车换乘次数的情况下找到城镇之间的联系

Question

如果给定适当的数据(城市列表、火车路线、火车站)，您会使用什么算法来创建能够返回用户选择的任意两个城市之间的连接列表的应用程序？应用程序必须仅选择那些落入可接受的火车换乘限制的连接。

示例:如果我需要从巴黎到莫斯科旅行，我会询问应用程序乘坐哪趟火车。 1 站/转车 - 应用程序返回路线:火车 1(巴黎-柏林)-> 火车 2(柏林->莫斯科)(不存在直接连接)。

图形示例

http://i.imgur.com/KEJ3I.png

如果我向系统询问从Town A 到Town G 的可能连接，我会得到回复:

• 棕线(0 转 = 直通)
• 棕色线到 B 镇/橙色线到 G 镇(1 个开关)
• 棕线到 B 镇/橙线到 D 镇/红线到 G(2 个开关)
• ...所有其他可能性

尽管第二个和第三个选项比第一个选项短，但应该优先考虑第一个选项(因为不涉及列车转换)。

Answer 1

假设唯一重要的是“停止/切换的次数”，那么问题实际上是在未加权的 directed graph 中找到最短路径.

图形模型是G = (V,E)其中 V = {all possible stations}和 E = { (u,v) | there is a train/route from station u to station v }
注意:假设您有一列从 a_0 开始的火车，路径经过 a_1、a_2、...a_n:那么 E 将包含:(a_0,a_1),(a_0,a_2),..,(a_0,a_n)还有(a_1,a_2),(a_1,a_3),...正式地:对于每个 i < j : (a_i,a_j) ∈ E.

BFS解决了这个问题，并且都是complete [如果有解决方案，总能找到解决方案] 和 optimal [找到最短路径]。

如果边 [routes] 被加权，类似于 dijkstra's algorithm将需要。

如果你想要一个所有可能路线的列表，Iterative-Deepening DFS可以在不维护访问集的情况下使用，并打印到目标的所有路径，直至相关深度。 [BFS 无法返回带有集团反例的所有路径]