Map Routing, a la Google Maps?

"Take a look at the open street map project to see how this sort of thing is being tackled in a truely free software project using only user supplied and licensed data and have a wiki containing stuff you might find interesting.

A few years back the guys involved where pretty easy going and answered lots of questions I had so I see no reason why they still aren't a nice bunch."

A* is actually far closer to production mapping algorithms. It requires quite a bit less exploration compared to Dijikstra's original algorithm.

"By Map Routing, you mean finding the shortest path along a street network?

Dijkstra shortest-path algorithm is the best known. Wikipedia has not a bad intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

There's a Java applet here where you can see it in action: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html and Google you lead you to source code in just about any language.

Any real implementation for generating driving routes will include quite a bit of data on the street network that describes the costs associate with traversing links and nodes—road network hierarchy, average speed, intersection priority, traffic signal linking, banned turns etc."

"Barry Brumitt, one of the engineers of Google maps route finding feature, wrote a post on the topic that may be of interest:

The road to better path-finding
11/06/2007 03:47:00 PM"