3.10.4. Алгоритм поиска критического пути

Пусть дана сеть (см. пример ниже). Для каждого события I определим наиболее Ранний срок Его наступления TP(I) По следующему правилу:

1) TP(0)=0;

2) для I >0 TP(I) Равно продолжительности самого длинного (0, I)-пути.

Значения Tp(I) Определяют последовательно, переходя от источника к стоку. Так, для рассматриваемого примера находим:

TP(0) = 0, TP(1) = 1, TP(2) = 5, TP(3) = 11, TP (4) = 11, TP(5) = 16.

Эти значения находятся из соотношения: TP(I) = max{ TP(K) + Tki } ,

Т. е. для всех дуг (K, I), для которых I является концом, необходимо вычислить TP(K) + Tki и выбрать наибольшее значение.

Итак, в нашем примере время выполнения проекта равно 16. Чтобы получить критический путь, будем передвигаться в обратном направлении, от стока к источнику, по тем ребрам (K, I), которые определяли значения TP(I), т. е. для которых выполняется равенство

TP(I) - Tki = TP(K) .

В примере это ребра: (3, 5); (2, 3); (2,1) . Таким образом, (1, 2, 3, 5) -- критический путь.

< Предыдущая		Следующая >