If you have two points p,q spacelike separated in a spacetime M there is not anything like the shortest spacelike curve joining them! Any spacelike curve joining them can be continuously deformed closer and closer to a lightlike curve joining the same points. So the inf of the set of the lengths of spacelike curves joining the points is always zero and this value is attained for a lightlike curve.
To answer your question we have to fix a reference frame. So, first of all we have to fix a family of spacelike 3-surfaces {Σt}t∈R whose union is the spacetime ∪t∈RΣt=M and pairwise disjoint
Σt∩Σt′=∅ for t≠t′.
Each Σt equipped with the positive metric induced by the one of the spacetime is a three dimensional rest space.
If you consider one of them, say Σ0 and fix p,q∈Σ0 (supposed to be connected), the shortest (obviously spacelike) curve belonging to Σ0 and joining them exists, if p and q are sufficiently close to each other, in view of a well known result of Riemannian geometry.
Very unfortunately all that I said above is theoretical, in the sense that it cannot be realized in practice. This is because "tempus fugit". I mean that you have to take time evolution into account, since an experiments is not an instantaneous procedure. So p and q have to better think of as the intersections with Σ0 of a pair of world-lines γp, γq describing the stories of material points. In view of time evolution, while you are performing experiments (searching for the shortest curve joining the points) in the interval of time [t1,t2], you are actually dealing with the whole subclass of rest spaces Σt with t∈[t1,t2].
Here a pair of problems arise.
(1) First of all the geometry of the Σt, that induced by the spacetime metric, can be different for every instant t.
(2) There is no trivial way to identify points belonging to different Σt
in order to define a notion of point at rest (at least during the interval of time [t1,t2]) with the considered reference frame.
The simplest way to get rid of both problems, without supposing unphysical instantaneous measurement procedures, is assuming that the spacetime admits a timelike Killing symmetry and that the Σt are compatible with that symmetry. This means that there is a family of disjoint timelike curves γr=γr(u) -- r varying in some set --
filling the universe and that, moving along one of them, the metrical properties of the spacetime remain fixed. Moreover the parameter t labelling the surfaces Σt coincides with the parameter u of each γr, so that
Σu is nothing but the evolution of Σ0 along the curves γu. t is the time parameter of the reference frame. The set of the indices r labelling the Killing curves γr can be identified to the points of Σ0 and, redefining the origin of t on each curve, we can arrange things in order that every curve γr intersects Σ0 exactly for t=0.
Within this picture, to come to your issue, we assume that γp and γq are two curves in the said family, and we can say that the material point whose γp and γq represent the stories are at rest with the reference frame ({γr}r∈Σ0,{Σt}t∈R).
Since the curves γr represent isometries, Σt1 and Σt2 have the same geometry that does not depend on time t. In other words the spacetime splits into the product R×Σ, where Σ is anyone of the Σt equipped with the induced (positive Riemannian) metric from the spacetime which, by construction, does not depend on time t. In particular, the distances
of γp(t) and γq(t), measured in each Σt do not depend on t.
Referring to the rest space Σ equipped with a static geometry we can safely answer your question. The shortest curve joining the two points (now at rest in the reference frame!) is the geodesic of the natural geometry on Σ. In practice, it can be constructed as the chain joining the points with the smallest number of links. Or you could adopt the parallel transport viewpoint: you have to construct an uninterrupted sequence of identical rigid rulers parallelly transported (the (n+1)th ruler is moved while remaining in contact with the nth) joining p and q. The length of the geodesic is the number of links in the first case or the number of rulers in the second case.