My problem is the following:
I have an undirected graph. Each edge has a cost (or weight). One of the nodes is labelled S. I want to start from S and visit every node at least once. Visiting a node multiple times is allowed. Travelling along an edge multiple times is allowed, although that would make the solution more expensive -- travelling an edge with 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 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.
A simple approach is to build the minimum spanning tree for your graph and do a (depth-first) walk over it, skipping nodes already visited.
This is proven to be no more than twice as long as the optimal TSP path. You can definitely do better with heuristics, but it's a starter (and easy to implement too).
What's a fast algorithm that can find a short path to traverse each node of a weighted undirected graph at least once?