title: What's a fast algorithm that can find a short path to traverse each node of a weighted undirected graph at least once?
body: <p>My problem is the following:</p>
  
  <p>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 <em>have</em> to travel an edge more than once.</p>
  
  <p>What is a fast algorithm to do this? Is this a well known problem? </p>
  
  <p>What I'm looking for:</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>I will be writing this in python. So if you know of any python implementation of the algorithm, that's best.</p>
  
  <p>Thanks for any help.</p>