# Shortest way to travel to each point in a set of points exactly once, and return to starting point?

Is there a polynomial time algorithm that finds this?

Just interested.

edit: In this case you are given a set of cartesian co-ordinates that represents their physical distance from one another.

-
What you are describing is the Traveling Salesman Problem, which is thought to have no polynomial time solution. –  A.E Jun 29 '13 at 4:35
Actually I thought it was kind of different, the TSP involves weighted graph, I'm talking about a set of co-ordinates on some two dimensional plane, or at least that's what I thought "points" would convey. –  user84348 Jun 29 '13 at 5:20
I'm not convinced the weighted graph can always be converted to a cartesian co-ordinate system. –  user84348 Jun 29 '13 at 5:54
If you are given a set of points in the Cartesian plane, you can construct a corresponding weighted graph for the TSP by weighting each edge between any two points according to the distance between them, using the formula: $$\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$$ –  Adriano Jun 29 '13 at 6:29
Sorry, Adriano I'm not asking to convert it that way round. Obviously you could solve my problem using TSP solutions, but I'm trying to ascertain whether this version of the problem (cartesian points) is simplified because I have cartesian values, and thus may not require exponential time solutions. –  user84348 Jun 29 '13 at 6:44

According to Wikipedia, the Euclidean traveling salesman problem is NP-complete, which implies that there is no known polynomial algorithm for finding the optimal solution. The Euclidean metric does simplify things, however, making it easier to find good approximative solutions, as described in the Wikipedia article on TSP.

-
Thanks. Next time I'll be sure to phrase my question better, don't like them down votes. –  user84348 Jun 29 '13 at 11:34