algorithm - 给定一组可能的起始节点，找到访问某些节点并返回的最小路径

Question

我有一组节点 (<= 10,000) 和边 (<= 50,000)，它们通过某种组合连接所有节点。也就是说，您可以使用至少一种边组合从任何其他节点开始访问任何节点。边的长度已定义。

我获得了一组必须通过的节点(最多 5 个)。所有这些都必须被访问，如果需要，我们可以多次通过它们。我们需要从一个非必须通过的节点开始我们的旅程，访问所有必须通过的节点，然后返回到我们的初始节点。

我们需要找到这样一条路径的最短距离。

假设我们有 5 个索引为 1, 2, 3, 4, 5 的节点和格式为 node -> node : length 的以下边(全部无向):

1 -> 2 : 1
1 -> 5 : 2
3 -> 2 : 3
3 -> 4 : 5
4 -> 2 : 7
4 -> 5 : 10

必须通过的节点是1, 2, 3。当我们从节点 5 开始时，可​​以实现最短距离，路径如下:5-1-2-3-2-1-5，因此行进距离为 12 。 12 是我们想要的输出。

有没有一种有效的方法来解决这个问题？

Answer 1

这是 O(E log V) 的解:

1. 让我们将起始节点视为必须通过的节点
2. 使用 Dijkstra 找到所有“必须通过”节点对之间的最短路径
3. 现在问题简化为 6 个城市的旅行商问题
4. 我们可以在 O(6!) 时间内检查所有排列，也可以使用 O(2^6 * 6^2) 的动态规划，因为 6 是常数，这部分的复杂度为 O(1)