在图中找到经过至少三个节点并以起始节点结束的路径的最短距离？

Question

我遇到了一个问题，需要找到解决方案的最优算法：在图中从起点到起点（形成一个循环），并访问至少三个不同的节点。例如，如果我们有一个图G(V,E)，其中V={a,b,c,d,e}且边缘E={(a,b,16),(a,c,300),(a,d,1),(b,c,100),(b,e,15),(c,a,10),(e,c,20)}，则最短距离将为61，并且它将访问a->c->e->b->a。

我考虑使用Dijkstra算法用于加权图，但是我不知道如何实现要求访问至少3个节点的限制部分？它看起来像哈密顿回路的问题，但没有使用所有节点，而只使用其中的一部分。这是NP完全问题吗？

任何帮助都将不胜感激。

- joy

Answer 1

实现这个算法的一种简单方法如下：

1. 预先计算所有节点之间的最短路径（例如使用Floyd–Warshall或对每个可能的起始节点运行Dijkstra算法）
2. 对于图中不同节点的每个元组（a，b，c），考虑从a到b，b到c和c到a的最短路径的连接。
3. 报告所有检查过的路径的最小值。

运行时间将由第二步支配，其运行时间为O(n³)。因此，问题不是NP-hard，因为我们必须访问的不同节点数是固定的（在本例中为3）。

- Niklas B.