Thread: shortest path

We all know that the shortest path between any two points is a straight line, and I'm certainly not disputing this fact, but what is the actual proof for it?

I suppose you mean in Euclidean space. I'll prove for n-dimensional space by induction.

For n = 1, this is trivially true, as all paths are straight lines.

Suppose it's true for some n ≥ 1. Then consider two points in n+1-dimensional space and a path between the two points. Take any n-dimensional hyperplane containing the two points. We can orthogonally project the path down to a path in this hyperplane. This new, projected path is at most as long as the original path--it moves in all of the same directions as the original path save for the direction orthogonal to the hyperplane. In fact, you can make this rigorous by considering the calculus definition of length--the length element for the new path would be bounded above by the length element for the old one because it's the same thing except movement in one direction has been changed to 0. In fact, this even shows that, unless the original path lies in the hyperplane, it is necessarily longer than the projected path, as the movement in this one direction must be nonzero at some point and hence on some interval. So, if our path is the shortest, it must lie in this n-dimensional hyperplane. But then the result for n dimensions says, for this new path to be shortest, it has to be a straight line.

Actually, I don't even need induction. My above proof shows that a shortest path between two points in n-space must lie in every (n-1)-dimensional hyperplane containing the two points, and you can show that the intersection of all such hyperplanes is the line between the two points.

When we're dealing with non-Euclidean space, we typically define lines by the property that they are the distance-minimizing paths through the space.

You can also do this by minimizing the corresponding functional equation. Do you know anything about the calculus of variations?

That is something I do not know. Care to enlighten?

Hey serpicojr

First we have to agree that a path is any C² function from R into the space in question. The maths is easiest to show for the 2d case so suppose (a₁, b₁) and (a₂, b₂) are two points in R² and that y=f(x) is a curve that joins those two points i.e. f(a_i) = b_i.

Now the length of that curve is given by the following integral ∫ L(x, y, y') = ∫ (1 + f'(x))^0.5 dx and we wish to minimize this integral over all C² functions such that f(a_i) = b_i. The Euler-Lagrange equations come to our rescue (I can derive them if you want, else take these on faith if you haven't seen them) and we find that f is a critical point of that integral if d/dt L_y' = L_y where the subscripts here denote partial derivatives.

This gives us the equation 0.5 d/dt (1+f'(x))^-0.5 = -0.25 (1 + f'(x))^-1.5 f''(x) = 0 which implies that f''(x) = 0 i.e. f is the straight line f(x) - b₁ = (b₂ - b₁)/(a₂ - a₁) (x - a₁)

I'm not sure about the C¹ case, will have to think about it.

I'm more than happy to assume C², although feel free to share if you do work out the C¹ case. I filled in the gaps with Wikipedia, which gives a pretty good proof of the Euler-Lagrange equation for the 2-dimensional case.

Oh, and I want to say that this proof is really slick!

I think I kind of got that, serpicojr. Thanks. As for river_rat's proof...I think I'll be saving that for a later time.

im in 8th grade and u all are confuzling but ill try to answer
i looked at this i took a pencil and put it in a strait line and then in a vertical line and it covers less of a distance going side ways then it does strait...

The important thing about Chemboy's question is that he's asking about paths between two specific points--i.e., he's asking about all possible ways to walk from point A to point B. There's only one line going through A and B, so we don't have to worry about any other lines when answering Chemboy's problem!

The things we do have to worry about are curved paths--how do we know that it's not shorter to take some sort of curvy route from A to B? Indeed, if we start looking at more complicated forms of this question--for example, finding the shortest path from New York to San Francisco--we have to start taking things into account like the varying landforms of (you may cover more distance going over a mountain than going around it) the United States and the curvature of the earth.