Shortest path to visit all nodes

问题:

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.

回答1:

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.