8.7.1. Длина дуг

Алгоритм Уоршалла позволяет ответить на вопрос, существует ли цепь (и, и). Часто нужно не только определить, существует ли цепь, но и найти эту цепь. Если задан орграф G(V, E), в котором дуги помечены числами (эти числа обычно называют весами, или длинами, дуг), то этот орграф можно представить в виде матрицы весов (длин) С:_{ О, для г = j Cij, конечная величина, если есть дуга из г в j, оо, если нет дуги из г в j.

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