# Shortest line for a bunch of points in postgis

I hava a very interessting problem, which I'm working on right now. I hava a dataset with a few points, and I'd like to know the shortest LINE to interconnect every point. No needs for routing etc. The result should be a sorted list with points or a linestring...

I'd realy appreciate your input, I have an idea about the concept but I don't know where to start. This nut is hard to crack. It's like a dijkstra-one-to-many problem, but without the routing, so should be easier and faster....

Thank you! Martin

edit:

-
You just need to connect all the points? Could you post a graphic to illustrate your problem and objective? – R.K. Oct 11 '12 at 10:27
Added a picture, it's for something like a microrouting to get en estimate idea. pgRouting will not work with this problem, as there are no nodes there... – Styp Oct 11 '12 at 12:10
Sounds like the traveling salesman without start = end node. – underdark Oct 11 '12 at 12:30
Thought about that! But how to do it in postgis, otherwise it will have unfortunate performance... – Styp Oct 11 '12 at 12:40
Of course this problem can be modeled as a network of nodes and edges and pgRouting can solve TSP pgrouting.org/docs/1.x/tsp.html – underdark Oct 11 '12 at 15:30

It would seem that what you want to accomplish is a Hamiltonian path.

In the mathematical field of graph theory, a Hamiltonian path (or traceable path), is a path in an undirected graph which visits each vertex exactly once.

PostGIS 2.0 has topology support so maybe you can implement it with that. Not sure if there are out of the box solutions though. Be warned that this is an NP-complete problem. Finding the path is a challenge in itself, let alone the shortest. Though if your points aren't that many then should be able to manage. Good luck.

-
The image in the question certainly shows no minimum spanning tree – underdark Oct 11 '12 at 15:28
Noted. Will find a better one. – R.K. Oct 11 '12 at 15:31
What I meant is that Martin seems to be looking for a solution that gives an ordered list rather than a tree. – underdark Oct 11 '12 at 15:58
Oh that. He just wants a line to to connect all nodes. x_x – R.K. Oct 11 '12 at 16:15
R has a PairViz package that has functions zigzag and hpaths. Might be useful. – klewis Oct 11 '12 at 18:53

Thank you for the input! I appreciate that. I found my solution and it works! For everyone else, who has a similar problem - read these articles on Wikipedia and start your research there:

And tbh the nearest neighbour is already a strong solution, with k-opt you can optimize, but to optimize 5% further down - you need a lot of time. I tested with my 'raw' data and had 10ms to get a nearest neighbour solution on 100 way points. But furtherdown the k-opt is running for several minutes...

-