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

Некоторые области применения:

• Определение наименьшего расстояния в сети дорог. 2 Вершины графа в таком случае представляют дорожные развязки, а рёбра — дороги, которые их соединяют. 2 Веса рёбер могут соответствовать протяжённости участка, времени, необходимому для его преодоления или стоимости путешествия по нему. 2
• Поиск оптимальной последовательности решений. 2 Если представить недетерминированную абстрактную машину как граф, где вершины описывают состояния, а рёбра определяют возможные переходы, то алгоритмы поиска кратчайшего пути могут быть применены для достижения главной цели. 2
• Поиск кратчайшего расстояния на карте. 14 Например, в компьютерных стратегических играх. 4
• Трассировка электрических соединений. 14 Алгоритмы поиска кратчайшего пути используются для прокладки соединений на кристаллах микросхем и на печатных платах. 14

Для решения задачи поиска кратчайшего пути на графе существуют различные алгоритмы, например: Дейкстры, Беллмана — Форда, A*, Флойда — Уоршелла, Джонсона и Ли. 12