Algorithm to connect all dots with the minimum total distance

Question

I have a set of points and a distance function applicable to each pair of points. I would like to connect ALL the points together, with the minimum total distance. Do you know about an existing algorithm I could use for that ?

Each point can be linked to several points, so this is not the usual "salesman itinerary" problem :)

Thanks !

Answer 1

What you want is a Minimum spanning tree.

The two most common algorithms to generate one are:

• Prim's algorithm
• Kruskal's algorithm

Answer 2

As others have said, the minimum spanning tree (MST) will allow you to form a minimum distance sub-graph that connects all of your points.

You will first need to form a graph for your data set though. To efficiently form an undirected graph you could compute the Delaunay triangulation of your point set. The conversion from the triangulation to the graph is then fairly literal - any edge in the triangulation is also an edge in the graph, weighted by the length of the triangulation edge.

There are efficient algorithms for both the MST (Prim's/Kruskal's O(E*log(V))) and Delaunay triangulation (Divide and Conquer O(V*log(V))) phases, so efficient overall approaches are possible.

Hope this helps.