# Shortest path with a start vertex that touches all nodes at least once with repeats allowed

I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I believe). Maybe I am over thinking this though? I'm not looking for the fastest solution, but I fear a brute-force algorithm may take an extremely long time to perform this on a undirected graph with say 30 nodes. I'm personally trying to figure out on a video game the fastest way to traverse through every spawn point of a monster on a given zone (with a start point of course) so I can find him faster. I've already constructed a graph and figured out the distances assuming a complete graph. I guess on my part, one way to reduce the run time of such an algorithm is to remove realistically what edges wouldn't and probably wouldn't be included in a optimal path. I assume adding lots of constraints could help too. Might anyone know if there's a specific name for this problem, or if there is a simpler approach aside from just the standard brute-force? Thank you!

• Can you clarify whether the path should go back to the start vertex? Are you interested in approximation algorithm? – John L. Dec 15 '18 at 12:14
• From your description it is not clear why this is not a TSP problem. – Vincenzo Dec 15 '18 at 16:59
• Sorry I should've said it explicitly. We don't want to go back to the start vertex, we just want to touch everything once! – Stawbewwy Dec 15 '18 at 19:07

## 1 Answer

Your problem is just a TSP in disguise.

## 1. Dealing with "visit each node at least once"

First, compute a modified distance matrix $$D(i,j)$$, $$i,j=1,...,n$$ using an all-pairs shortest path algorithm, such as the Floyd-Warshall algorithm. That is, you want $$D(i,j)$$ to be the shortest path length from node $$i$$ to node $$j$$. Using Floyd-Warshall you also compute a matrix $$S(i,j)$$ that gives the successor of $$i$$ on the shortest path from $$i$$ to $$j$$.

Now apply a TSP algorithm to the distance matrix $$D$$. This will give you a tour $$T$$ that goes through each node exactly once. You now expand each step of $$T$$ into a shortest path (you can do this using the matrix $$S$$). That is, if some step of $$T$$ goes from $$i$$ to $$j$$, you expand it into the shortest path from $$i$$ to $$j$$. Concatenating all these paths gives a tour $$T'$$ that visits each node at least once, with possible repeats. If $$T$$ is optimal for $$D$$, then $$T'$$ must be optimal for the original graph.

## 2. Dealing with "the tour does not need to return to the starting node"

Preprocess your graph as follows. Add a dummy node, node 0, such that the distance from 0 to the starting node $$s$$ is 0 and the distance from node 0 to any other node is $$M := n \cdot \max_{i,j} D(i,j)$$.

Now find a TSP tour on the modified graph using your TSP algorithm of choice. Because the value of $$M$$ is so large, any optimal TSP tour will be of the form $$0, s, \pi(1), ..., \pi(n-1), 0$$ where $$\pi$$ is some permutation of the nodes excluding the start node and node 0. Then the sequence $$s, \pi(1), \ldots, \pi(n-1)$$ represents your solution.

## 3. Exact vs heuristic

You can use any algorithm for the symmetric TSP problem. If $$n$$ is about 30, you will probably not be able to apply an exact (= optimal) TSP algorithm such as the Held-Karp dynamic programming algorithm. A very simple yet reasonable heuristic you might want to try is 2-OPT, which is straightforward to program. A branch-and-bound approach might also work well in practice.

• I guess a question then to ask is, what's the last step to not return to the start node? – Stawbewwy Dec 15 '18 at 19:13
• Thank you for the amazing details :) I wish I could upvote your answer, but I don't have enough reputation! – Stawbewwy Dec 16 '18 at 7:39