This has been bugging me for about two weeks now..
I have a cartesian plane with n number of points randomly placed on it. You can get the coordinates of each point. Now, how do you calculate the shortest distance to connect all of them. ie. A to D to C to F to B to E?
I have asked my Highschool Math Teacher, she simply replied, "You would use common sense."
I want to calculate it mathematically… Any ideas?
Best Answer
This really isn't a shortest-path problem per se, since you're not just finding the shortest path between a pair of vertices, but it is a graph theory problem. It is most emphatically not solvable by "common sense".
If you don't have to connect the points in a chain, (e.g. you are allowed to connect A,B,C,D by connecting A to each of the other three) then this is a minimum spanning tree problem, and can be solved by Prim's Algorithm (http://en.wikipedia.org/wiki/Prim%27s_algorithm) or Kruskal's Algorithm (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm) efficiently. If not, this is a special case of the Travelling Salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem) which is computationally difficult.
Unless you know something special about how the points are chosen, you probably aren't going to get out of computing most of the $\binom{n}{2}$ distances between them.