algorithm - 如何找到地铁或铁路网络的最少换乘次数？

Question

我知道 Dijkstra 算法可以找到两个节点(或者在地铁站的情况下)之间的最小距离。我的问题虽然涉及找到两个站点之间的最小传输次数。此外，在所有最小传输路径中，我想要时间最短的路径。

现在为了找到一条最小换乘路径，我使用了一个专门应用于地铁线路的 BFS，但它不能保证找到的路径是所有其他最小换乘路径中最短的。

我在想，也许修改 Dijkstra 的算法可能会有所帮助 - 通过试探性地为每次传输添加权重(时间)，这样它会阻止算法传输到不同的线路。但在这种情况下，我需要凭经验找到转移权重。

问题补充:

有人建议我在每次算法想要换乘不同的地铁线路时添加一个“惩罚”。在这里，我解释了我对此的一些担忧。

我把这个问题搁置了几天，今天又回来了。再次查看问题后，似乎在站点上执行 Dijkstra 算法并找出传输发生的位置很难，它并不像人们想象的那么明显。

举个例子:如果这里我有一个部分图表(只有 4 个站点)和它们的地铁线路:A(红色)、B(红色、蓝色)、C(红色)、D(蓝色)。设A站为源。连接是:
---- D(蓝)- B(蓝、红)- A(红)- C(红)-----

如果我遵循 Dijkstra 算法:最初我将 A 放入队列，然后在第一次迭代中将 A 出列并查看其邻居:B和C，我根据权重A-B和A-C更新它们的距离。现在即使 B 连接两条线，此时我也不知道如果我需要在 B 进行转账，那么我不添加转账的“罚款”。假设 A-B < A-C 之间的距离导致 B 的下一次迭代出队。它的邻居是 D 并且只有在这个我看到转移必须在 B 进行。但是 B 已经被处理(出队)。 S

所以我不确定这种在确定传输需求时的“延迟”将如何影响算法的完整性。有什么想法吗？

Answer 1

您可以将每个权重设为一对:(# of transfers, time)。您可以以明显的方式添加这些权重，并按字典顺序比较它们(首先比较传输次数，使用时间作为决胜局)。

当然，正如其他人所提到的，使用 K * (# of transfers) + time 对于一些足够大的 K 会产生相同的效果，只要你知道最大先验时间并且你不知道不要用完您的重量存储空间。