Shortest route with no set destination in Google Maps V3?

Question

So I'm just learning javascript to mess with the Google Maps API. I was wondering if anyone had an elegant solution to this problem I'm running into.

A Google Maps route request must contain three things (origin, destination, and travelMode). My travelMode will always be DRIVING. The origin will always be wherever the user is located.

The destination though, needs to vary. I have several waypoints and the user will visit, and would like to provide the shortest trip possible depending on what waypoints are selected and where the user is, ending the route at one of the waypoints (eg: ABC or ACB, but always Axx...x).

Is there any possible way to do this other than calculating every possible path and seeing which has the shortest distance (or time, or whatever I'm evaluating on)? It seems like that would be prohibitively costly (O(n!)).

edit: With the suggested optimizeWaypoints flag set to true this becomes a O(n) problem instead of O(n!), but now I have issues with issuing too many requests in too short of a time period.

Answer 1

There is a setting in google directions to provide optimized route (optimizeWaypoints - http://code.google.com/apis/maps/documentation/javascript/services.html#Directions ) you simply set it to true in your directions object

Answer 2

If you want the shortest route you can call first to Google distanceMatrix API and get the sort list of stops.

Then call to API directions with the sort list.

Answer 3

A simple solution would be to specify Origin and Destination as the same and ask Google Maps to optimize the route based on all other waypoints. It will usually either go to the farthest point first, or last, then come back to the origin. You could then make another request without optimizing, this time specifying the Destination as the last optimized waypoint.