I work for a small development company in the process of tackling this problem. We are building a social network (don't ask my why.. but the client pays..), and need to calculate the shortest path between any two members (IE, friend of a friend of a friend). This, essentially, is the traveling salesmen problem.
Although our solution may change, currently we are attempting to use the
Dijkstra Algorithm as a stored SQL procedure. Of course, this approximates the shortest path, but the result is good enough for our needs, and based on the original post, probably good enough for a Google Maps app as well.