graph-theory - 最短的方式，超过 2 点，但修复订单

Question

首先，请原谅我英语不好。

我遇到了以下问题：我必须以固定顺序（例如 A -> D -> F）找到 2 个以上点之间的最短路径。我熟悉 Dijkstra 的算法。但是那个只计算两点之间的最短路径。我也听说过 TSP，但这似乎也不合适。因为没有修复顺序。我已经在网上搜索了我的问题，但也许这不是一个很受欢迎的问题，或者我使用了错误的关键词。

尽管如此，还是要有一个解决方案，因为有很多路线规划器，都成功地提供了这个功能。

所以拜托，任何人都可以通过命名一个算法来帮助我解决我的问题，或者给我一些建议。

非常感谢您的帮助！你真诚的，安杰洛

//edit 呵呵，很尴尬。看来我想了很久，所以我没有描述真正的问题。就是这样：有一些票，只能从头使用。

T1：A -> B（费用 50） T2：B -> C（费用 50） T3：A -> B -> C（费用 80） 给定路线是 A -> B -> C

现在你看，如果我们将给定的路线视为两个独立的问题，我们的总成本将变为 100，但显然 Ticket T3 是更好的解决方案。

Answer 1

如果某些点是固定的，而其他点则不是（意味着用户想要从A->D->F，但图表意味着他们可能必须这样做A->B->C->D->E->F）这是一个标准问题。您要么关心 ADF 订单，要么不关心（可能是 AFD）。在第一种情况下，它是A->D D->F您独立计算的简单的两条路径 ( )。在第二种情况下，它更像是 TSP。

Answer 2

您可以找到 A 和 D 之间的最短路径，然后是 D 和 F 之间的最短路径等。对每对节点多次应用 Dijkstra 算法。