# Finding the shortest path in a fully-connected undirected graph

I am trying to solve a problem in which I have a list of two-dimensional coordinates, and I want to find the shortest path that connects all of them.

At first I thought this was a case of the Traveling Salesman Problem, however:

• You don't need to get back to the starting city, which I believe TSP wants you to.
• On this two-dimensional plane where we work with the euclidean distance metric, the triangle inequality holds, which the normal TSP algorithms don't care about, if I recall correctly.
• There is no 'you only can visit a node once' rule in this problem; the 'shortest path' could form a tree.

I then thought to 'just make a graph and use Prim's or Kruskal's algorithm to find the (length of the) minimum spanning tree'. However, the graph representations commonly used are either an adjacency matrix, which seems a waste for an undirected graph, or an adjacency list, which is slower for a sparse graph (and a fully-connected graph is of course the exact opposite of sparse).

I have the feeling that I am discarding information this specific problem has, which will result in using more time and/or memory that would be required to solve the shortest connecting path problem for a fully-connected, undirected graph in 2d-space.

So:

• What would be the most efficient practical data representation to store this graph in?
• What would be the most efficient algorithm to find the length of the shortest path connecting all nodes?
• Possibly dumb question: if the triangle inequality holds, why would you ever visit a node twice? Mar 26, 2017 at 23:35
• @PhilipKendall What I mean is that the optimal path might form a tree, not necessarily a 'snake' as the TSP requires.
– Qqwy
Mar 27, 2017 at 9:30