Крутчайший путь в графах больших размерностей.

[abash]

Уважаемые специалисты,
Подскажите, пожалуйста, каким образом в автомобильных навигационных системах реализуется алгоритм поиска кратчайшего пути. Есть понимание, что, как правило, это делается с помощью алгоритма Дейкстры и т.п., но каким образом удается избежать огромных вычислений, связанных с необходимостью пройти все вершины графа? Как система понимает, что если мне надо проложить маршрут в пределах Москвы, то не стоит проверять перекрестки , скажем, Владивостока? С другой стороны, если изначально оставить в графе только вершины имеющие региональный признак Москва, вдруг обнаружится, что с заездом в Московскую область маршрут окажется короче (или взять к примеру приграничый город Женева).
Вроде как алгоритм А* оптимизирует алгоритм Дейкстры, стоит на нем остановится? Или есть варианты получше?
Не хочется изобретать велосипед, т.к. навярняка, гораздо более умные люди уже об этом думали и оптимальные решения найдены.
Заранее благодарен.