Компьютерные сети. Лабораторные работы
Легко заметить, что такой граф
Легко заметить, что такой граф должен быть бесконтурным .
Нашей задачей является нахождение самого длинного пути из вер-шины s , соответствующей началу проекта, до вершины t , соответствующей его окончанию. Такой путь называется критическим. Его длина определяет время, необходимое для реализации всего проекта. Эта задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса A( u,v ), где u -> v , на обратный. Так, например, выполните предыдущую программу для следующей путевой матрицы:
Пример 4 [Библиотека,1975,с.100-104].
Планирование критического пути (анализ сети ПЕРТ).
PROGRAM C_r_i_t_P_a_t_h;
{ Автор алгоритма : Leavenworth B. (CACM,1961,3) }
type Massiv = Array [1..20] of Integer;
var n : Integer ; { Общее количество работ по проекту }
{ (количество ребер ориентированного графа) }
i : Massiv ; { Вектор-пара, представляющая k-ю работу, }
j : Massiv ; { которая понимается как стрелка, связыва - }
{ ющая событие i [ k ] с событием j [ k ] }
{ Граф задан массивом ребер: }
{ ( i [1], j [1]),( i [2], j [2]),...,( i [ n ], j [ n ]) }
{ Должно быть выполнено: }
{ i [1]=1, i [ k ]< i [k+1], i [ k ]< j [ k ] }
dij : Massiv ; { dij [ k ] - продолжительность k-й операции }
s1 : Massiv ; { s1[ k ] - самый ранний срок начала k-й }
{ операции }
s2 : Massiv ; { s2[ k ] - самый поздний срок начала k-й }
f1 : Massiv ; { f1[ k ] - самый ранний срок завершения k-й }
f2 : Massiv ; { f2[ k ] - самый поздний срок завершения k-й }
{ операции }
tf : Massiv ; { tf [ k ] - полный резерв времени k-й операции}
ff : Massiv ; { ff [ k ] - свободный резерв времени k-й }
{ операции }
k : Integer ; { Параметр цикла }
{ ----------------------------------------------------------- }
PROCEDURE C_r_i_t_i_c_a_l_P_a_t_h (n: Integer; i: Massiv;
j: Massiv; dij: Massiv;
var s1,s2,f1,f2,tf,ff: Massiv);
var k,index,max,min: Integer;
ti,te : Massiv;
BEGIN
index:=1;
For k:=1 to n do
begin
If i[k]=index+1 then index:=i[k];
ti[k]:=0; te[k]:=9999
end;
