1) I will first show how to compute the distance between point $q$ and the line $(p_1,p_2)$.
Let $u$ be the vector $\vec{p_1p_2}$ and let $v$ be the vector $\vec{p_1q}$.
You want to find the orthogonal projection $p$ of $q$ on the line.
This is given by the formula
$$
p=p_1+\frac{(u,v)}{\|u\|^2}u.
$$
Once you have $p$, you distance is simply the distance between $q$ and $p$, namely
$$
d(q,p)=\|\vec{qp}\|.
$$
Note: $(u,v)$ denotes the Euclidean inner-product and $\|u\|=\sqrt{(u,u)}$ the Euclidean norm.
2) Now let us consider the distance to the segment $[p_1,p_2]$. Recall that $p$ is the orthogonal projection of $q$ on the line.
There are three cases:
a) The projection $p$ belongs to $[p_1,p_2]$, then your distance is $d(q,p)=\|\vec{qp}\|$.
b) The projection $p$ belongs to $(-\infty,p_1)$, the infinite portion of the line which starts at $p_1$ excluded and does not contain $p_2$. Then your distance is $d(q,p_1)=\|\vec{qp_1}\|$.
c) The projection $p$ belongs to $(p_2,+\infty)$, the infinite portion of the line which starts at $p_2$ excluded and does not contain $p_1$. In this case, it is $d(q,p_2)=\|\vec{qp_2}\|$.
3) How to make this an algorithm.
3.1) Compute
$$
\frac{(u,v)}{\|u\|^2}.
$$
3.2) If this is in $[0,1]$, you are in case a), so compute $p$ and return $d(q,p)=\|\vec{qp}\|$.
3.3)If this is negative, you are in case b), so return $d(q,p_1)=\|\vec{qp_1}\|$.
3.4) If this is greater than $1$, you are in case c), so the answer is $d(q,p_2)=\|\vec{qp_2}\|$.
I believe this is robust, since this never leads to a division by $0$.
I think a more fundamental way to approach the problem is by discussing geodesic curves on the surface you call home. Remember that the geodesic equation, while equivalent to the Euler-Lagrange equation, can be derived simply by considering differentials, not extremes of integrals. The geodesic equation emerges exactly by finding the acceleration, and hence force by Newton's laws, in generalized coordinates.
See the Schaum's guide Lagrangian Dynamics by Dare A. Wells Ch. 3, or Vector and Tensor Analysis by Borisenko and Tarapov problem 10 on P. 181
So, by setting the force equal to zero, one finds that the path is the solution to the geodesic equation. So, if we define a straight line to be the one that a particle takes when no forces are on it, or better yet that an object with no forces on it takes the quickest, and hence shortest route between two points, then walla, the shortest distance between two points is the geodesic; in Euclidean space, a straight line as we know it.
In fact, on P. 51 Borisenko and Tarapov show that if the force is everywhere tangent to the curve of travel, then the particle will travel in a straight line as well. Again, even if there is a force on it, as long as the force does not have a component perpendicular to the path, a particle will travel in a straight line between two points.
Also, as far as intuition goes, this is also the path of least work.
So, if you agree with the definition of a derivative in a given metric, then you can find the geodesic curves between points. If you define derivatives differently, and hence coordinate transformations differently, then it's a whole other story.
Best Answer
I'll just do $\Bbb R^2$, but the extension should be clear. Let the point be $(a,b)$ and the segment from $(c,d)$ to $(e,f)$. Parameterize the segment as $(c+t(e-c),d+t(f-d))$. The distance is a linear function of $t$, so can have no local maximum or minimum. You just need to check the endpoints and the points where it is no longer differentiable. So check $(c,d),(e,f)$ and the values of $t$ where $c+t(e-c)=a$ or $d+t(f-d)=b$