c++ - 在至少访问 X 节点一次的图中查找最短路

Question

尽管我还是初学者，但我喜欢解决与图形相关的问题(最短路径、搜索等)。最近我遇到了这样一个问题:

Given a non-directed, weighted (no negative values) graph with N nodes and E edges (a maximum of 1 edge between two nodes, an edge can only be placed between two different nodes) and a list of X nodes that you must visit, find the shortest path that starts from node 0, visits all X nodes and returns to node 0. There's always at least one path connecting any two nodes.

Limits are 1 <= N <= 40 000 / 1 <= X <= 15 / 1 <= E <= 50 000

这是一个例子:

红色节点 ( 0 ) 应该是路径的起点和终点。您必须访问所有蓝色节点 (1,2,3,4) 并返回。这里的最短路径是:

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 with a total cost of 30

我考虑过使用 Dijkstra 找到所有 X(蓝色)节点之间的最短路径，然后贪婪地选择最近的未访问 X(蓝色)节点，但它不起作用(提出 32 而不是纸上的 30 ).我后来还注意到，仅仅找到所有 X 节点对之间的最短路径将花费 O(X*N^2) 时间，这对于这么多节点来说太大了。

我唯一能找到的电路是欧拉电路，它只允许访问每个节点一次(我不需要那个)。这可以用 Dijkstra 解决还是有任何其他算法可以解决这个问题？

Answer 1

这是一个可能足够快的解决方案:
1) 从每个蓝色节点运行最短路径搜索算法(这可以在 O(X * (E log N)) 中完成)以计算成对距离。
2)构建一个只有零个顶点和蓝色顶点(X + 1 个顶点)的新图。使用第一步计算的成对距离添加边。
3)新图足够小，可以使用动态规划求解TSP(时间复杂度为O(X^2 * 2^X))。