CODEWITHSUNDEEP
graph-theoryshortest-pathtraveling-salesman
Jonathan
Jonathan

Reputation: 165

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 taken 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

Upvotes: 2

Views: 611

Answers (2)

Ante
Ante

Reputation: 5448

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).

Upvotes: 1

Nicolas Grebille
Nicolas Grebille

Reputation: 1332

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.

Upvotes: 1

Related Questions