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.

  • $\begingroup$ Define "good" approximation. MST gives a trivial 2 approximation for the TSP. $\endgroup$
    – lox
    Jun 29 '19 at 19:51
  • $\begingroup$ what is a 'trivial 2 approximation' ? $\endgroup$
    – Jacco
    Jun 29 '19 at 20:13
  • $\begingroup$ He means it's never more than twice the optional route. See here. $\endgroup$ 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})$$

  • $\begingroup$ Thanks for your interesting answer. However, I don't understand how it answers the question? Why is the euler tour introduced? $\endgroup$
    – Jacco
    Jun 30 '19 at 9:03
  • $\begingroup$ $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 $\endgroup$
    – lox
    Jun 30 '19 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.