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