Methods and apparatus for generation of a route from a source location to a final destination are described. According to one embodiment, a two-ended search is performed based on the principles of the A* algorithm. That is, two routes are simultaneously generated, one from the source to the destination, and one from the destination to the source. According to another embodiment, a route generation algorithm determines when to stop searching for route candidates. The algorithm searches a map database for a first number of iterations thereby generating a first route candidate. After generation of the first route candidate, searching of the map database is terminated after a second number of additional iterations. A best route candidate is then selected as the route.