Alex Rivera | Logout

Algorithm to connect all dots with the minimum total distance

Asked 2012-02-27T19:32:06.657
9

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 !

algorithm
Edit
Report

1 Answer

2

The algorithm you are looking for is called minimum spanning tree. It's useful to find the minimum cost for a water, telephone or electricity grid. There is Prim's algorithm or Kruskal algorithm. IMO Prim's algorithm is a bit easier to understand.

answered 2012-02-27T19:39:30.957

Your Answer