I would put my data into an R* Tree then run a DBSCAN algorithm over it to break it down into clusters O(n * lg(n)). Once the points have been clustered you can then find the cluster that's closest in size to the number of points you want to find the shortest path between. Since you've broken everything down to just 10 points you have two options you can either: Solve the Traveling Salesman Problem for the points which is slow O(n!) and precise, or take the leftmost point and get the shortest path to the rightmost point using Dijkstra's algorithm which is much faster O(E + V * log(V)) but doesn't give you the optimal result.
EDIT!
As pointed out in the comments below using Dijkstra's algorithm here would result in O(n!+V * log(V)) since any path between two points is an edge. It would be faster to use the Held–Karp algorithm to solve the TSP which runs O(n^2 * 2^n)