访问所有节点的最短路径 [英] Shortest path to visit all nodes

问题描述

我正在寻找一种对我来说非常典型的算法，但看起来常见的解决方案只有一点点不同。

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

旅行推销员问题似乎增加了限制，即每个节点只能访问一次，并且路径必须返回到开始位置。

最小生成树可以是解决方案的一部分，但这样的算法只提供树，而不是最小的路径。另外，因为它们是树，因此没有循环，所以它们强制回溯到循环可能更有效的地方。

可以通过变换图来将其减少到正常的旅行推销员问题。首先，计算每对节点的最小距离。你可以使用Floyd-Warshall算法。一旦你拥有了它，只需构建一个完整的图，其中节点之间的边是从em到u到em的最小开销。然后，您可以应用普通的TSP算法，因为您不必再​​次访问节点，这已经隐藏在边缘成本中。

I'm looking for an algorithm that seems very typical to me, but it seems that the common solutions are all just a little bit different.

In an undirected graph, I want the shortest path that visits every node. Nodes can be revisited and I do not have to return to the start node.

The Travelling Salesman Problem seems to add the restriction that each node can only be visited once and that the path has to return to where it started.

Minimal Spanning Trees may be part of a solution, but such algorithms only provide the tree, not a minimal path. Additionally, because they're trees and therefore have no loops, they force backtracking where a loop may be more efficient.

解决方案

You can reduce it to the normal Travelling Salesman Problem by transforming the graph.

First, compute the minimum distance for every pair of nodes. You can use Floyd-Warshall algorithm for that. Once you have it, just construct the complete graph where the edge between nodes u and v is the minimum cost from u to v.

Then, you can apply a normal TSP algorithm as you don't have to revisit nodes anymore, that's already hidden in the costs of the edges.

这篇关于访问所有节点的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！