Algorithm for connecting all points with a 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 points together with a minimum total distance. Do you know about an existing algorithm that I could use for this?

Each point can be associated with several points, so this is not a common "seller" problem :)

Thanks!

Answer 1

You want a minimal spanning tree .

The two most common algorithms for generating one of them are:

• Prim algorithm
• Kruskal's algorithm

Answer 2

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

First you need to create a graph for your data set. To effectively form an undirected graph, you can compute triangulation

Answer 3

The algorithm you are looking for is called a minimal spanning tree. It is useful to find the minimum costs for water, telephone or electrical network. There is a Prim algorithm or a Kruskal algorithm. IMO Prim algorithm is a little easier to understand.

Answer 4

here http://en.wikipedia.org/wiki/Minimum_spanning_tree you can find additional information about the minimum spanning tree so that you can adapt it to solve your problem.

Answer 5

Take a look at Dijkstra's algorithm:

Dijkstra's algorithm, conceived by the Dutch scientist and programmer Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the shortest path problem of a single source for a graph with non-negative costs for edge paths, creating the shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

http://en.wikipedia.org/wiki/Dijkstra 's_algorithm