Microsoft have announced that the route planning engine on Bing Maps has been switched over from "a modified Dijkstra's algorithm" to the excitingly named "Customizable Route Planning Algo." The real-time planning and routing is being processed twice as fast as the Dijkstra method.

The CRP routing engine comes with some special sauce too. We exposed a feature in the API for alternate routes, so when you’d like to see additional options for the route you can request up to 3 routes in one request using the maxSolutions method. You can then display them on the map for visual reference.

There's even more detail and technical points at Microsoft Research if you're interested:

We present an algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach supports turn costs, enables real-time queries, and can incorporate a new metric in a few seconds---fast enough to support real-time traffic updates and personalized optimization functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in memory simultaneously.

More at the Bing Blog.