[ot]

These slides summarize pretty much all the recent developments in shortest path algorithms:

http://research.microsoft.com/en-us/people/goldberg/erice.pd...

There are example with maps overlaid with the nodes visited by each algorithm before finding the solution. The difference between Dijkstra, A* and landmarks-based algorithms is impressive!