algorithm - 访问所有节点的最短路径

Question

我正在寻找一种对我来说非常典型的算法，但似乎常见的解决方案都略有不同。

在无向图中，我想要访问每个节点的最短路径。可以重新访问节点，而不必返回到起始节点。

旅行商问题似乎增加了每个节点只能访问一次并且路径必须返回到起点的限制。

最小生成树 可能是解决方案的一部分，但此类算法仅提供树，而不是最小路径。此外，由于它们是树，因此没有循环，因此它们会在循环可能更有效的地方强制回溯。

Answer 1

您可以通过转换图形将其简化为普通的旅行商问题。

首先，计算每对节点的最小距离。您可以为此使用 Floyd-Warshall 算法。一旦你有了它，只需构建完整的图，其中节点 u 和 v 之间的边是从 u 到 v 的最小成本.

然后，您可以应用普通的 TSP 算法，因为您不必再​​重新访问节点，这已经隐藏在边的成本中。