Does anyone know how Mapquest works? I do a lot of programming myself, and I can’t figure out for the life of me how they would code that. I understand they have a giant DB with roads, intersections, etc, but how do they actually figure which is the shortest route?
My guess is that they use some sort of successive approximation algorithm, and apply the law of diminishing returns to get a route that, though it may not be the shortest, is still pretty close.
Massive Dijkstra’s algorithm?
Given that the map is two dimensional, and given you know the length of the road segments, I wouldn’t imagine a shortest-path graph algorithm faring too badly.
That’s what I was thinking, but if you imagine the number of road segments in the US, it gets to be pretty damn big, and Mapquest usually returns results within a second or two. Perhaps they have some kind of localization feature added in to speed up the most common cases?
You might want to look up a technique called A*, which can bias the search based on some measure of how close a choice gets you. It turns out that with a properly constructed ‘acceptable’ heuristic, you can still get an optimal solution. It just gets there faster. If you design a poor heuristic, you might get a suboptimal solution… but if you’re not far off from acceptable, you’ll get a nearly optimal one.
Constrained to a 2d map, distance covered could be a good heuristic. It would bias the search very directly between the two points.
But there are other ways to optimize it too, and maybe even weight the paths on other than drive distance to complicate matters. 
I’m a GIS programmer. Never set up any routing, but deal a lot with linear data. Most of my work is with polygons, which of course is made of lines.
These lines have endpoints that can intersect with other lines. They also have vertices that do not intersect with other lines. All of these have X,Y coordinates.
Also, the origination, and the to destination have X.Y coordinates.
I don’t know how it’s done, but this is how I would take a shot at it.
Buffer the straight line between the origination and destination. A buffer selection allows you to select all lines (roads/records) within a certain distance of the ‘crow flies’ line. For a thousand mile trip, buffer 250 miles, or whatever. This could be adjusted based on road density for an area. Or scenic route or speed or whatever. Every line or road segment is a record that carries all these attributes.
At this point, you have eliminated 99% of the database.
Now it’s pretty easy to make some calculations, and re-buffer if need be. It’s an excersise in diminishing returns.
A database always need some item, some field, some link to be able to communicate with other information. Every ‘thing’ has a location. The lowest common denominator is where that item is. Where it is physically located.
GIS can relate a fire plug to a house. And does. Nothing similar, other than where they are located.
Fun stuff.
Now if I can only get this chip out of my head……
That makes sense to me. I once used MapQuest to calculate the route to two different houses on the same street in a subdivision. There was only one road into the subdivision. However, it gave two completely different routes to the entrance to the subdivision. So the route calculation must have been using an algorithm including the geographical location of the destination rather than just adding up the bits of road to get there.
Thank you, thank you, thank you.
It’s just data, with a little geography on the side.
North is up, right? 
Hamsters, it is all done with hamsters running around until they all congregate on a given point. Driving instructions are done the same way only with two teams of hamsters. One team starts at the start position and the other team starts at the destination. They run around until they hook up. Absolutely amazing, don’t you think? 
Straight from Mapquest’s About Mapquest page:
It doesn’t go into any further details on “spatial technology”, but it would seem that enipla’s description would be similar to this.
They have a scaled model of the map. They put a bunch of hamsters it the starting point and a piece of cheese at the finish point and note the route the fastes hamster took. That is why they have a disclaimer that the system is not always accurate: sometimes a hamster is tired or not hungry.
Yep, we call them spatial databases.
I’m working on address ranges for a road network at the moment. This will allow us to ‘geo-code’ an address database. In other words, it will relate an x,y coordinate for a paticular address. We will then be able to link it to a reverse 911 application. This gives us a way to select an area on a map and send out an automated phone call to all those folks that live in that area. Good for natural disasters and such.