Работа с картами

понятно, что точный алгоритм на NP полной задаче ляжет

Поиск расстояния между двумя городами — это не NP.

http://project-osrm.org/ кажется должно подойти.

не напрямую, а по дорогам,

автомобильным, железным, пешеходным? Земля круглая или плоская? Разницу высот надо учитывать? Физически существующие, но по политическим причинам непроходимые дороги?

Не между двумя, а между одним и всеми остальными из списка с отбором n ближайших городов для каждого города из списка. Пересекающиеся и разветвляющиеся улицы и дороги тоже учитывать надо.

автомобильным, железным, пешеходным?

В первую очередь автомобильным, железные тоже хорошо если есть. Земля круглая, разница высот не важна, проходимые, т.е. границы государств и закрытые зоны учитывать.

Вот за него спасибо. Жалко там железки нет, а выглядит очень подходящим

Можно еще на pgRouting посмотреть. Решение более универсальное по сравнению с OSMR.

единственный свободный и бесплатный граф дорог есть у openstreetmap.
набор готовых роутеров смотреть здесь https://wiki.openstreetmap.org/wiki/Routing
,jkmibycndj bp большинство из них опенсорс - копируй к себе и запускай.

Смотри на тему роутинга по OSM, API куча: graphhopper, OSRM, чёто ещё нынче напоявлялось. Естественно, открытые и бесплатные. Там же данные в любых форматах.

ЗЫ

Ещё хочется чтобы космических требований к памяти не было, а то как-то печально когда библиотека, пусть и быстрая хочет 175 гигабайт оперативки на это дело.

Если ты используешь (любое) API, тебе не нужно памяти под данные вообще.

А если ты сам собираешься строить маршруты, то должен понимать что геоданные, тем более всего мира - очень тяжёлая вещь по своей сути, поэтому чтобы использовать их напрямую (из своего кода или из библиотеки) нужно либо много памяти в которую они влезут, либо база данных которая будет быстро читать их с диска по мере необходимости (postgresql + postgis), причём базу сначала нужно будет налить (несколько часов). Либо данные нужно специально готовить - как минимум, вырезать только дороги и сильно упростить граф (тебе же не нужна форма дорог между перекрёстками, только длина), но на это само по себе нужна память и время.

Но я не думаю что тебе нужно этим заморачиваться когда есть API. Результаты из него, к слову, можно кэшировать на довольно долгое время (дни - недели), это поможет если тебя не устраивает доступность, latency или нужно слишком дофига RPS.

дык не натягивай роутинг на всю землю :)

тебе нужна-то всего одна девятая часть суши с очень небольшой плотностью дорог.

Потенциально мне весь мир надо натягивать и с большими нагрузками, но там ладно, надо будет натянут за бабосы

для облегчения обрезать дороги уровня track, пешеходные, конные ... тебе же не по лесам роутить
как вариант еще и service, если во дворы заезжать не собираешься.

потребности сильно полегчают

ну и в https://web.telegram.org/#/im?p=@ruosm https://forum.openstreetmap.org/viewforum.php?id=21 стукнутся

Я бы вообще убрал все дороги в городах, они не важны. А вот дорога в лесу между городами важна, даже если она плохая.

А вот дорога в лесу между городами важна, даже если она плохая.

Ремонтировать машину кто будет потом? Почему в нашей стране люди с таким отношением?(

Что мешает строить чуть длиннее маршруты, но по нормальной дороге? Человечнее надо... И у водителя будет возможность срезать и нарваться на проблемы в дороге, если его рабовладелец одобрит такое.

Надеюсь, что чушь про «выбор» я не услышу.

Я не навигацию пилю, а связность населенных пунктов смотрю. Это немножко про другое.

дорога в лесу между городами важна, даже если она плохая.

В прошлом году дороги были, на картах есть. В этом году все буреломом завалило, дороги исчезли!

Кто-нибудь знает нечто подобное?

В инете есть кучу хороших готовых решений. На много больше чем тебе здесь накидали ссылок.