How is routing done on maps?
rchiniquy: Check out http://www.openstreetmap.org. They provide open-source map data and code (like rana which has a module for routing) that does least-cost routing. There are a variety of approaches based on simple graph algorithms like naive A*.