A Traveling Salesman Variant

Question

Is their a variant of Traveling Salesman Problem or other algorithms about the following problem:

Say G is an incomplete undirected weighted graph. V is a subset of vertices of G.

How to find a simple closed circuit along V (and probably some other vertices of G), which has a minimal weight between each two vertices of V.

Thank you

---------------------- edit ------------------------

Is there a name or published document or related research paper for this problem?

Answer 1

First, because V (which is a subset of vertices of G as you state) is itself a weighted graph - calculate the edges of V first so you can ignore G.

For example this input of G:

G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb)

Can be simplified to this input of V:

Va -- 15 meter --> Vb

The fun starts when you have the input has multiple paths between to V vertices (with no other V vertices in between):

G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb)
G1 (Va) -- 7 meter --> G4 (no V) -- 7 meter --> G3 (Vb)

Then the simplified form is (it takes the second route):

Va -- 14 meter --> Vb

Use the Dijkstra algorithm during that simplification.

Second, apply a good TSP algorithm on V. It's NP-complete so there is no perfect algorithm. There are many available frameworks depending on your programming language (java, C/C++, ...).