algorithm - 在图形中查找路径通过最少三个节点并以起始节点结束的最小距离？

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's algorithm对于加权图，但是我不知道如何实现访问最少 3 个节点的约束部分？它看起来像哈密顿循环的问题，但没有使用所有节点，而是只使用其中的一部分。这是 NP 完全问题吗？

如有任何帮助，我们将不胜感激。

Answer 1

一个简单的实现方法如下:

1. 预先计算所有对的最短路径(例如使用 Floyd–Warshall 或为每个可能的起始节点运行 Dijkstra)
2. 对于图中不同节点的每个元组 (a, b, c)，考虑从 a 到 b、b 到 c 和 c 到 a 的最短路径的串联。
3. 报告所有检查路径中的最小值。

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