Алгоритмы? Дык, это..... Теория графов.
Но не тех графов, которые с баронами и князьями, а тех, которые из прикладной математики
Думаю, в основном, классический алгоритм Дейкстры
https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Точнее, как мне подсказал товарищ VF, в нави-программах используется более продвинутый вариант алгоритма Дейкстры под названием A-star.
https://ru.wikipedia.org/wiki/Алгоритм_поиска_A*
Ну а дальше уже возможны разные ********ия. Например, перекрёсток можно представить не в виде одной вершины графа, а в виде маленького под-графа, где каждый манёвр на перекрёстке представлен отдельной дугой. При таком подходе можно, например, левым поворотам поставить большее значение "трудности проезда", чем при движении прямо или направо. А запрещённый поворот на перекрёстке означает просто отсутствие соответствующей дуги графа.
Кроме того, в каждой дуге в свойствах можно ввести параметр "запрет движения таким-то категориям тр. средств". При этом при расчёте маршрутов эта дуга просто не будет рассматриваться, если, к примеру, в настройках указан "грузовик", а движение грузовых а/м там запрещено. Что, кстати, забыли сделать в Libelle, поэтому она строит маршрут по пешеходным проходам и дорожкам
Ну, ещё вот из возможных наворотов:
В Навителе 5, как я понял, используется таблица предпоследних точек маршрутов.
То есть, сначала компьютер просчитывает кратчайшие маршруты между каждой парой вершин графа. Потом записывает в таблицу предпоследний пункт в каждом маршруте.
В дальнейшем по этой таблице легко и быстро восстанавливается любой маршрут, потому что навигатору не надо пересчитывать маршрут. За него это сделали раньше. Однако, такая таблица занимает много места на флешке. Что, собственно, и видно по размеру файлов карт России. Карта России в nm3 заметно прибавила в весе по сравнению с картой в nm2, хотя новых дорог там нарисовали не так уж и много.
