Если все строки обработаны, выполнение
Если все строки обработаны, выполнение алгоритма заканчивается.
Если все выбранные таким образом элементы, образующие множество {?1j(?)}, ? = 1, ... , kj, отличны от нуля, полагаем ?1j = max ?1 j? + tj.
Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.
Обработанную j-ю строку метим, чтобы исключить её повторную обработку. Переходим к выполнению шага 2.
Примечание. Если граф G не содержит контуров, зацикливание при этом невозможно.
Конец алгоритма.
Если матрица S треугольная, то никогда не складываются условия для многократного циклического обзора строк. Тогда ранние сроки окончания выполнения работ находятся за один последовательный просмотр строк матрицы S.
Очевидно, что Tкр = max {?11 , ... , ?1m}.
По матрице S* ( S — треугольная) на рис. 7.5 (граф G — на рис. 7.1) находим
?11 = t1 = 2, ?12 = t2 = 3, ?13 = ?11 + t3
=3, ?14
= ?11 + t4 = 4, ?15 = max {?11, ?12 + t5= 7, ?16 = max {?11, ?14} + t6 = 8, ?17 = max {?12,?14 } + t7 = 6, ?18 = max {?13, ?15, ?16, ?17} + t8 = 9; Tкр = 9.
Чтобы рассмотреть пример с нетреугольной матрицей следования, выберем граф G без контуров с "неправильно" пронумерованными вершинами (рис. 7.10).
Рис. 7.10. Информационный граф с не треугольной матрицей следования
После обработки первой строки ?11 = 1. Попытка обработать вторую строку неудачна, т.к. ?13 и ?14 ещё не найдены. После обработки третьей строки ?13 = ?11 + t3 = 3. Обработка четвёртой строки даёт ?14 = 2. После обработки пятой строки ?15 = ?13 + t5 = 4. Попытка обработки шестой строки неудачна, т.к. не найдено значение ?12. Приступаем к следующему циклу обзора необработанных строк S. Обрабатываем вторую строку: ?12 = max {?13, ?14} + t2 = 6.
