Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once).

In order to solve this problem, I have found that we can compute the shortest paths and weights ($p_{i,j}$, $w_{i,j}$) between all pairs of nodes in the graph and then construct a new graph that has an edge between node i and j with weight $w_{i,j}$ and label $p_{i,j}$. We can then run a regular TSP solver on this graph and get the path. Finally, this path is expanded out by using the $p_{i,j}$ labels on the edges.

I have two questions. 1) When finding shortests paths between all pairs of nodes, it is possible that two paths between node i and j may exist giving the same minimum weight. When expanding back out the solution from the TSP solver, we must choose which one is correct. Does this mean I must minimize over all possible combinations of these paths? E.g. if I have 2 paths between A-B and 3 paths between C-D, I need to test all 6 possible combinations?

2) If we assume an asymmetric graph instead of a symmetric one, can this problem be solved by following the techniques for conversion given here https://en.wikipedia.org/wiki/Travelling_salesman_problem#Asymmetric_TSP ? Are there better methods for doing this (since now we have to solve a 2N node problem vs the original N node problem).

• You may be interested in this lecture note from 2009, which remarks at the bottom of page 1 that the relaxed problem allowing nodes to be visited more than once is equivalent to a version of TSP in which the edge weights satisfy a triangle inequality, essentially imposing a metric distance for the edge weights. The remark leaves the proof of this equivalence as an exercise for the Reader. Attention is then devoted to what is termed Metric-TSP and its approximation. See also its references. – hardmath Jun 2 '16 at 12:50