algorithm - 所有节点的非循环路径

Question

是否有一种算法或一组算法可以让您找到距任意起始节点的最短步行距离，以便在权重无向图中访问每个节点？它不完全是旅行推销员，因为我不在乎一个节点是否被多次访问。（即使你回到起点也没关系——只要它是访问所有节点所需的最后一个节点，walker 就可以最终到达某个遥远的节点。）它不是最小生成树，因为可能 A-->B-->C-->A-->D 是访问 A、B、C 和 D 的（非唯一）最短路径。我的直觉说这不是这不是一个 NP 问题，因为它没有使 NP 问题如此棘手的限制。当然，我可能完全错了。

Answer 1

来自维基百科关于旅行推销员问题的文章：

去除每个城市“只访问一次”的条件并不能去除 NP 硬度，因为很容易看出，在平面情况下，存在只访问每个城市一次的最优旅游（否则，根据三角不等式，一条捷径跳过重复访问不会增加游览长度）。

Answer 2

不确定在已接受答案的问题中添加答案的礼仪是什么。

我添加这个答案只是为了不必跳转到另一页，不必处理平面图和三角形不等式，而且这很简单并且可能更容易理解。

哈密​​顿路径问题可以简化为：

假设我们有一个多项式时间算法来解决我们找到访问所有顶点的最小权重游走的问题。

给定一个我们需要确定是否存在哈密顿路径的图，我们只需将其原样提供给手头的问题算法，设置边权重 = 1。如果算法返回的值 > n-1，那么原图中没有哈密顿路径，否则有。

所以这个问题是NP-Hard。