Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

Question

I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints:

• a complete, connected, weighted graph,
• vertices are defined in 3d euclidean space,
• relatively low number of vertices (less than 500)
• no limits on how many times a node may be visited
• a fixed starting vertex
• no requirement for which vertex to end at.

I've looked at minimum spanning tree algorithms, but those could create sub-optimal result, because they optimize for lowest summed edge weight.

I'm suspecting this may be a variant of the traveling salesman problem and thus NP-hard. For our use case however, a good approximation will be good enough.

Answer 1

Suppose $G$ is a weighted graph, and $T_{OPT}$ is the optimal route you seek.

For clarity: $T_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices, it holds that $w(T_{OPT}) \leq w(P)$.

Denote $M$ for the MST of $G$. Since $T_{OPT}$ is a subgraph of $G$ that connects all its vertices, we can say:

1. $w(M) \leq w(T_{OPT})$ - by definition of MST.

Denote $M^*$ An euler tour of $M$. Since $M^*$ visits each edge of $M$ exactly twice, it holds that:

2. $w(M^*) = 2w(M)$
3. $M^*$ is some path that visits all vertices of $G$, hence a path that solves your problem (although we cannot say $w(M^*) = w(T_{OPT})$)

Following from 1. 2. and 3. we get:

$$w(M) \leq w(T_{OPT})$$ $$2w(M) \leq 2w(T_{OPT})$$ And, since $w(M^*) = 2w(M)$ $$w(M^*) \leq 2w(T_{OPT})$$