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?