在图中找到至少访问一次X节点的最短电路

Question

虽然我还是初学者,但我喜欢解决与图形相关的问题(最短路径,搜索等).最近我遇到了这样的问题:

给定具有N个节点和E边缘的非定向加权(无负值)图形(两个节点之间最多1个边缘,边缘只能放置在两个不同节点之间)和一个必须访问的X节点列表,找到从节点0开始的最短路径,访问所有X节点并返回到节点0.总是至少有一条路径连接任意两个节点.

限制为1 <= N <= 40 000/1 <= X <= 15/1 <= E <= 50 000

这是一个例子:

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

0 - > 3 - > 4 - > 3 - > 2 - > 1 - > 0,总成本为30

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

我唯一可以找到的电路是Eulerian电路,它只允许访问每个节点一次(我不需要它).这可以用Dijkstra解决,还是有其他算法可以解决这个问题？

Answer 1

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