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

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.

• Define "good" approximation. MST gives a trivial 2 approximation for the TSP. – lox Jun 29 '19 at 19:51
• what is a 'trivial 2 approximation' ? – Jacco Jun 29 '19 at 20:13
• He means it's never more than twice the optional route. See here. – BlueRaja - Danny Pflughoeft Jun 29 '19 at 20:42

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:

1. $$w(M^*) = 2w(M)$$
2. $$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})$$

• Thanks for your interesting answer. However, I don't understand how it answers the question? Why is the euler tour introduced? – Jacco Jun 30 '19 at 9:03
• $M^*$ is a traversal of $G$ as requested, with a cost not more than $2 * OPT$. If you're asking "Why does the euler tour of the MST gives this approximation?" then a proof is added to the answer – lox Jun 30 '19 at 13:48