虽然我还是初学者，但我喜欢解决与图形相关的问题（最短路径，搜索等） . 最近我遇到了这样的问题：
给定具有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解决，还是有其他算法可以解决这个问题？
1 回答
这是一个可能足够快的解决方案：
1）从每个蓝色节点运行最短路径搜索算法（这可以在O（X *（E log N））中完成，以计算成对距离 .
2）仅构建一个零顶点和蓝顶点的新图（X 1顶点） . 使用在第一步中计算的成对距离添加边 .
3）新图足够小，可以为TSP使用动态编程解决方案（它具有O（X ^ 2 * 2 ^ X）时间复杂度） .