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

Question

是否有一种算法或一组算法可以让您找到距任意起始节点的最短步行距离，以便在权重无向图中访问每个节点？它不太像旅行商，因为我不关心一个节点是否被多次访问。 (如果你回到起点甚至都没有关系——步行者可以在某个遥远的节点结束，只要它是访问所有节点所需的最后一个节点即可。)它不是最小生成树，因为 A-->B-->C-->A-->D 可能是访问 A、B、C 和 D 的(非唯一)最短路径。我的直觉告诉我这不是这不是一个 NP 问题，因为它没有使 NP 问题变得如此棘手的限制。当然，我可能完全错了。

Answer 1

来自维基百科关于 Travelling Salesman Problem 的文章:

Removing the condition of visiting each city "only once" does not remove the NP-hardness, since it is easily seen that in the planar case there is an optimal tour that visits each city only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit would not increase the tour length).