Компьютерные сети. Лабораторные работы




Система дорог - часть 6


Легко заметить, что такой граф должен быть бесконтурным .

Нашей задачей является нахождение самого длинного пути из вер-шины 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;



Содержание  Назад  Вперед