Определение

Пусть в графе или орграфе ‑ это последовательность ребер, по которым можно поочередно проходить.

Другими словами, путь из вершины А в вершину В начинается в А и походит по набору ребер до тех пор, пока не будет достигнута вершина В.

С формальной точки зрения, путь из вершины в вершину – это последовательность ребер графа , , …, .

При этом требуется, чтобы любая вершина встречалась на таком пути не более чем один раз. У всякого пути есть длина – число ребер в нем (Рисунок 6).

Рисунок 6 – Путь в графе. В данном случае имеет место два пути из вершины А в вершину В, определяемых суммой длин дуг:

для пути – ;

для пути – .