Mathematica surprisingly doesn't have a built in find shortest path function for unspecified ends. We do however have FindShortestTour.
I was unimpressed by stack exchanges recommendation of 'try most possibilities'.
A shortest path is essentially a shortest tour where we visit an extra point once. This extra has to be equidistant from all the actual points, so that the path can begin and end anywhere. Visiting the extra must be prohibitively costly, such that it's never a short cut between our actual points. Then at the end we cut the extra out so we have a path through our points, rather than the returned cycle.
As FindShortestTour takes custom distance functions, we can build a function like this easily. Notably this is faster than constructing and computing the graph equivalent.
This code specifies a distance function that is euclidean for numeric coordinates, and 10^10 for symbolic coordinates (appropriate for my application). This distance function is used to find the shortest cycle through a set of points and a symbolic extra, and then the result is cut back to the shortest path.
PuncturedDistance[a_, b_] :=
If[And[NumericQ[a[[1]]], NumericQ[b[[1]]]], EuclideanDistance[a, b],
If[Xor[NumericQ[a[[1]]], NumericQ[b[[1]]]], 10^10, 0]]
findShortestTour[set_] := (
tour = FindShortestTour[Append[set, {p}],
DistanceFunction -> PuncturedDistance][[2]];
Join[tour[[ Position[tour, Length[set] + 1][[1, 1]] + 1 ;;]],
tour[[2 ;; Position[tour, Length[set] + 1][[1, 1]] - 1]]])
