Для построения маршрута в памяти устройства должен быть сохранён граф дорог, по которому и будет поиск. Алгоритм для поиска выбирается в зависимости от потребностей. Самые простые — это алгоритм Дейкстры и А*. 2Гис недавно в своём блоге описывал интересный алгоритм для офлайн маршрутизации на устройствах с ограниченной памятью
