How to find the least cost to visit every vertex in an undirected, weighted graph at least once starting from a predetermined vertex?

The path tak开发者_StackOverflow社区en does not have to end back at the predetermined vertex. Basically, the traveling salesman problem except that a vertex can be visited more than one time.

EDIT: There will be up to a maximum of 10,000 vertices and edges

---

Not sure about it, but I think it's optimal (maybe not the most efficient thought): compute the minimal path between each pair of points, and then apply the traveling salesman on this graph.

---

Since, in standard TSP definition, solution is Hamiltonian cycle (or tour), it doesn't have to be optimal. In practice TSP is an optimization problem to find the shortest tour, like you described it.

Problem is still NP-hard, and it is solved with algorithms that find near-optimal solutions. This is one of result you get searching for "Heuristics for the Traveling Salesman Problem" (pdf).