Графы применяются в оптимизации маршрутов для нахождения кратчайших расстояний с минимальными затратами. 1

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

Каждому ребру сопоставляют критерий выгодности, который определяется целью оптимизации маршрута. 1 Чаще всего в качестве критерия принимается минимум суммарного пробега. 1 Также могут использоваться такие показатели, как платность или загруженность дорог, частота пересечения данной дорогой населённых пунктов и другие. 1

Для решения задачи оптимизации маршрутов на основе графов используются различные алгоритмы, например, Дейкстры и Флойда-Уоршалла. 25