1. A route calculation program for use in a navigation system used with a map database stored on a computer readable storage medium, the route calculation program adapted to find a solution route between a first location on a road network in a geographic region and a second location on the road network in the geographic region, said route calculation program comprising: at least one search tree adapted to hold a plurality of gate data structures, each of said gate data structures representing a physical position on the road network in the geographic region represented by said map database and a direction from said position to another location on said road network in said geographic region, said at least one search tree associated with said first location; and a priority queue referencing said gate data structures in said at least one search tree and assigning a priority to one of said gate data structures; wherein said route calculation is adapted to expand said one of said gate data structures to determine successor gate data structures thereof and to compare each of said successor gate data structures to gate data structures associated with said second location.