算法:找到城镇之间的连接,限制列车的变化

Question

您将使用什么算法来创建给定适当数据的应用程序(城市列表,列车路线,火车站)能够返回任何两个用户选择的城市之间的连接列表？应用程序必须只选择那些属于已接受的列车更改限制的连接.

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

图形示例

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

如果我向系统询问从A 镇到G 镇的可能连接,我会收到回复:

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

而且你的第二和第三选项比第一选项更短,它应该是优先考虑的第一选项(因为不涉及列车切换).

Answer 1

假设唯一重要的是"停止/切换次数",那么问题实际上是在未加权的有向图中找到最短路径 .

图模型在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解决了这个问题,并且完整 [总是找到解决方案,如果有的话]并且最优 [找到最短路径].

如果边[路线]被加权,则需要类似dijkstra算法的东西.

如果你想要的清单所有可能的路由,迭代式深化DFS可以使用,无需维护拜访集,打印所有发现目标到相应深度的路径.[BFS无法使用clique的计数器示例返回所有路径]