Non-cycle path to all nodes

Question

Is there an algorithm or set of algorithms that would let you find the shortest walking distance from an arbitrary start node so that every node gets visited in a weight, undirected graph? It's not quite Traveling Salesman, because I don't care if a node is visited more than once. (It doesn't even matter if you make it back to the start -- the walker can end up in some far-off node as long as it was the last one needed to visit all nodes.) It's not quite minimum spanning tree, because it may be that going A-->B-->C-->A-->D is a (non-unique) shortest path to visit A, B, C, and D. My intuition says that this isn't quite an NP problem, because it doesn't have the restrictions that make NP problems so tricky. I could, of course, be completely wrong.

Answer 1

From Wikipedia's article on 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).

Answer 2

Not sure what the etiquette is to add an answer to a question with an already accepted answer.

I am adding this answer just for the sake of not having to jump to another page, to not have to deal with planar graphs and triangle inequality and the fact that this is simple and probably easier to understand.

Hamiltonian Path problem can be reduced to this:

Suppose we had a polynomial time algorithm to solve our problem of finding a least weight walk which visits all vertices.

Given a graph of which we need to decide a hamiltonian path exists or not, we just feed it as it is, to the problem algorithm at hand, setting edge weights = 1. If the algorithm returns a value > n-1, then there is no hamiltonian path in the original graph, else there is.

So this problem is NP-Hard.