In the absence of an answer from someone on the Google Maps team, I feel obliged, based on my credentials which I list at the end of this post, to update my answer to provide more detail and clarity. The post with edits by Iddo Gino certainly deserves a good share of views and upvotes, but Iddo’s post still understates the complexity of mapping and navigation technology. I’m posting details here to make more clear how much more complex this question is than a simple Dijkstra algorithm can solve. Dijkstra is only a tiny part of it. A* is even less important. For algorithm buffs, all that Dijkstra adds to the map technology is the idea to use a priority queue. (Apologies, I cannot resist this: http://www.drdobbs.com/architecture-and-design/priority-queues-for-motorists/184405153).

Let’s start with the original question: How does the algorithm of Google Maps work? The question is misleading because maps and navigation systems have many algorithms including:

• Spatial indexing algorithms and algorithms of computational geometry to organize the map data and retrieve it efficiently.
• Algorithms to draw maps (e.g. project latitude and longitude coordinates, fill the polygons, place names for streets, cities, businesses, parks, …).
• Algorithms to understand queries from users (NLU or NLP)
• Algorithms to process GPS signals (on which I am much less expert than on other topics here)
• Algorithms to perform what is called geocoding, converting addresses to points (or polygons) on a map.
• Algorithms to perform reverse geocoding, converting points to addresses using point in polygon algorithms (another example of using computational geometry).

I’ll get to the route calculation algorithms, but let me mention more of the other complex aspects of maps and navigation especially those relevant to computing routes.

• Gathering and organizing the data: it can come from many different sources. Just one example of a very complex problem that arises from that is the very messy geometry that results when the map coordinates from two sources (latitude, longitude) are in slight disagreement – especially polygons and lines. Besides data about roads, data about addresses, business, parks, malls, and institutions are needed.
• Iddo mentions “costs”. Yes that’s important and not at all trivial for various reasons. The costs are the “weights” on the graph’s edges to use the terminology of graph theory, but computing those weights accurately is complex. Here are some complex parts of determining costs:
• Collecting and using traffic data so that slow roads are less likely to be chosen in the route calculation.
• Estimating future costs when route is long and is driven in the future.
• Time to travel through intersections of roads. All navigation products take into account the differences in time needed to make different turns at an intersection because the times can vary significantly – left turns usually take much longer than right turns but not always. And the many and complex varieties of configurations of intersections make this a challenging problem.
• Additional parameters to consider are fuel costs and the complexity of the route. If a route with a few turns is only slightly longer than a route with many turns, it is likely to be a better choice for the driver.
• I mentioned intersections. The diagram below might provide some idea how difficult it is to deal with intersections because not every turn is allowed. The restrictions shown must be encoded into the graph used by the route calculation algorithm.

Okay I’ll discuss route calculation algorithms themselves but remember it’s only one component of many in the map and navigation technology. As some have mentioned computing a route a long way across a large map can be expensive and slow. So optimizations of the Dijkstra are needed:

• A*. A* has been a very important concept in traditional AI, and many route calculation algorithms include it. But, in my experience in developing the algorithms, A* offers only a minor improvement in performance – maybe 30%. For other applications in AI, the graphs might be very different in such a way the A* provides a larger performance advantage, but not much for road networks.
• Bi-directional. This is a somewhat more effective optimization and almost all route calculation algorithms in the industry use it but not primarily for the performance advantage it brings. It means that the route is computed both forward from the origin (with Dijkstra, A*, reach-based routing, highway hierarchies, contraction hierarchies, or other methods) and backward from the destination. Like A*, the technique reduces the area searched, but more importantly, some more important algorithms (ones using road hierarchies) require it to work. But bi-directional route computations bring their own complications – the algorithm must determine when the two searches have met at a point on an optimum or near optimum route and that’s more complex than it sounds.
• Using the road network hierarchy. This is the most important performance optimization and was used long ago at companies like Etak in a practical but not academically formal way. My invention and paper on reach-based routing brought the concept into academia and spawned further research producing algorithms like Highway Hierarchies and Contraction Hierarchies. Since the lead author of the papers on Highway Hierarchies, Peter Sanders, gave a talk at Google, it has been speculated that Google has used Highway Hierarchies:

• Shortcuts. This concept replaces sequences of edges with single edges in the preparation of the graph. The concept was used in industry before I published my paper and I regret not having space to mention it under Further Work in my paper. The folks at Karlsruhe in Germany took full advantage of shortcuts in Highway Hierarchies and Contraction Hierarchies.
• Other issues affecting the algorithms:
• Even if we ignore performance, Dijkstra does not solve all problems. One problem is time-dependency. Sometimes the algorithms must allow the costs on the edges to change depending on the time that the route brings the user to particular point on the roads.
• For example, the road might be closed at a particular time.
• Or traffic might be predicted to become worse.
• Most of the fast algorithms require processing on the map data before any routes are computed, but some of the data affecting that “pre-processing” changes quickly, e.g. traffic data. Determining what part of the problem is solved in pre-processing and what part is solved during the route calculation and how it is solved is very difficult.

This diagram shows some history of the algorithms:

One final list of complexities that map and navigation technologies face:

• Guidance: how is the user instructed on the route and when?
• Detecting when the driver has gone off the route and needs a new route.
• Special requirements depending on the type of transportation
• Bicycles which cannot legally use all roads.
• Electric vehicles needing to be charged along the route.
• Use of trains and buses
• Trips that combine different modes of transportation including walking
• Where will the vehicle park? That’s not trivial in city centers like San Francisco.
• What if the navigation device (e.g. cell phone) can only hold map data for nearby areas but the driver is on a long trip that sometimes travels out of the cell network.
• Keeping map data up to date on cell phones.
• Differences between states and countries that affect
• Rules for using roads.
• Language and addressing systems supported by geocoding.
• 3D map data – organizing and displaying it. Complex 3D graphics algorithms here.

My credentials:

• I worked at one of the very first companies to provide digital maps for drivers, compute routes for them, and use GPS to provide guidance – Etak.
• I worked at start-up, Airflash, which developed some the first map and navigation apps for cell-phones.
• I wrote the aforementioned article for Dr Dobbs.
• I developed route calculation algorithms at Wavemarket (now called Location Labs)
• I wrote a highly cited and important paper on the topic of route calculation. Here’s the whole story: Ron Gutman's answer to What is the best programming algorithm that you have ever created?
• I worked on mapping at Yahoo.
• I worked on maps and navigation using GPS and mobile phones at Telenav where I read many papers on the topic of route calculation.
• Some related patents.