What's a fast algorithm that can find a short path to traverse each node of a weighted undirected graph at least once?

Question

My problem is the following:

I have an undirected graph. Each edge has a cost (or weight). One of the nodes is labeled S. I want to start from S and visit every node at least once. Visiting a node multiple times is allowed. Traveling along an edge multiple times is allowed, although that would make the solution more expensive -- traveling an edge with the cost of 3 twice will add 6 to the cost of the total path. The graph has some "dead-end" nodes, so sometimes we have to travel an edge more than once.

What is a fast algorithm to do this? Is this a well-known problem?

What I'm looking for:

Reasonably fast -- The relative size of the graph we are talking about here is an order of 40 - 50 nodes. So the algorithm hopefully won't take longer than 10 - 15 seconds.

Reasonably optimal -- I'm not looking for absolute optimality. Any interesting heuristic to guide the search so that the solution will be near-optimal is good enough.

I will be writing this in python. So if you know of any python implementation of the algorithm, that's best.

Thanks for any help.

Answer 1

The big difference between standard TSP and your algorithm is that TSP usually enforces only one visit per node, whereas you are allowing multiple visits. A simple method is to build the minimum spanning tree for your graph and do a (depth-first) walk over it, skipping nodes already visited.

This is declared to be no more than twice as long as the optimal TSP path. You can surely do better with heuristics, but it's a starter (and easy to implement too).

for more information regarding the same, refer to the following link:

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial and Artificial Intelligence Course. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.