# 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