0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hardmath Jun 2 '16 at 12:50
0
$\begingroup$

Further discussion with another person on this makes me feel that Question 1 is resolved. I can in fact choose any of the paths since they will all be of same weight and won't affect the answer. I was worried that one path might not lead to visiting all nodes while another would, however this possibility is eliminated since we already ran TSP on the modified graph - e.g. all nodes in the graph are already in the path.

I'm still interested in the 2nd question.

$\endgroup$
  • $\begingroup$ For future reference, note that the original Question can be edited to include additional information. Particularly since the revision is given shortly after the Question was posted and doesn't invalidate any Answer that may be offered, it would be an improvement to the Question. $\endgroup$ – hardmath Jun 2 '16 at 12:37

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.