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.