It's obvious that it's used in stuff like Google Maps, but what are some more metaphorical applications where you're minimizing the path between nodes (which can represent anything)
[Math] Non-literal applications of “Shortest Path” algorithm
algorithmsrecursive algorithms
Related Solutions
There are many algorithms for computing shortest paths on polyhedral 2-manifolds.
With a student I computed the shortest paths shown below with one, the Chen-Han algorithm.
The algorithms fan out shortest paths to a frontier, mimicking the structure
(but not the details) of Dijkstra's algorithm for shortest paths in a graph. Sometimes the method is called the "continuous Dijkstra" method. These algorithms (all in $\mathbb{R}^3$) are described in many places, including
the book Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 24.
I would assume the same approach will work for triangulated manifolds in arbitrary dimensions, but of course it will be significantly more complicated to implement.
As Emre says, it's probably a corporate secret, but I would guess that they've just optimized the heck out of some well-known algorithm. You can find info about such algorithms by starting here.
Best Answer
I'm not sure this is "non-obvious", but you can use a shortest path algorithm to numerically solve calculus of variations boundary value problems (i.e. where you know the starting and ending values). This can be done, for example, by creating a 2D grid of points, for example:
The integral you want to minimize is a path integral which takes the form:
$$ S = \int g(f, \dot{f}, t)dt $$
You can approximate this integral using edges that connect two grid points. The weight of the edge is the approximate value of this piece of the integral. That is, you estimate the $\dot{f} \approx \frac{\Delta f}{\Delta t}$, then plug into $g$ and approximate the integral as $\int_t^{t + \Delta t} gdt \approx g\Delta t$. You have to introduce a lot of extra nodes to create edges in many different directions (from each node) to accurately solve the problem. Once you have the graph setup (the nodes and edges with their edge weight), you simply solve the shortest path problem to find the solution from a starting node to an end node (or you could do an all-pairs shortest path algorithm to find a more general solution).
Here's an actual example of using this to find an optimum path to take between two polygonal lines using something very similar to dynamic time warping (this actually is an invariant DTW scheme). The first solution requires monotonicity and the second doesn't. If you don't know anything about free space diagrams, the white regions represent points (from both lines) that are less than a certain distance from each other. You can see that the non-monotonic solution sort of tends towards the middle of the free space:
If you want more information, you can read Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves (it's a PDF). They explain all of this in more detail (and present a translation invariant measure).
Caveat
It's worth pointing out that this algorithm fails for some problems. Specifically, it fails for problems where the solution is a sinusoid. If you try to apply this problem to a harmonic problem (specifically one where the solution should be a sinusoid) it fails miserably. Now part of this is that periodic solutions are not that amenable to boundary value problems. The problem with those is that the boundaries often can result in many different solutions.
...and this is the rejected (and I think for good reason actually) paper where I discussed this in more detail...