Графы в системах навигации применяются для поиска кратчайшего пути. 2 В случае дорожной сети города и перекрёстки — это вершины графа, а дороги между ними — рёбра. 12 Если известна длина каждой дороги, то это будет значением (весом) рёбер графа. 1

Один из алгоритмов, который используется для этого, — алгоритм Дейкстры. 1 Он позволяет не перебирать все варианты, а находить самый короткий путь только между соседними графами и так, шаг за шагом, продвигаться к конечной точке. 1

Также в системах навигации для поиска маршрута габаритного объекта по цифровой карте местности используется навигационный граф. 3 Его вершины (ячейки) представляют собой окружности (в трёхмерном случае — цилиндры), внутри которых находится свободное от препятствий пространство, а рёбра, соединяющие вершины, — отрезки, образующиеся точками пересечения окружностей. 3