В GPS-навигаторах для поиска кратчайшего пути применяется алгоритм Дейкстры. 13 Он позволяет рассчитать оптимальный маршрут между двумя узлами взвешенного графа или сети. 3

Принцип работы: при введении начальной и конечной точки маршрута навигатор изучает расположение и длины графов, реорганизует все графы воедино и пытается определить все объекты, которые наиболее приближены к точке назначения. 1

Главным условием для работы такого алгоритма является наличие векторной карты, которая представляет собой набор объектов (в основном дорог), отображаемых на дисплее навигатора. 3 Благодаря этому можно учитывать ориентацию и положение машины в текущий момент времени. 3

Также при поиске маршрута навигатор учитывает сложность маршрута и реальное время: в графы добавляется время прохождения поворота, чтобы алгоритм искал быстрый маршрут с учётом геометрии дорог. 2