关键路径算法2

关键路径算法2:

  若结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动，如下图。

可使用如下算法:

(1)求活动最早可以开始的时间

     eet[1]:=0;eet[k]:=max(eet[j]+r[j,k])

(2)求活动最迟应该开始的时间

     et[n]:=eet[n];et[k]:=min(et[j]-r[k,j]);

(3) 关键路径通过点J，具有如下的性质：eet[j]=et[j]

程序如下:

program gao7_6;
var i,j,n,max,min,w,x,y:integer;
    r:array[1..20,1..20] of integer;
    eet,et:array[1..20] of integer;
begin
  readln(n);
  for i:=1 to n do
    for j:=1 to n do
      r[i,j]:=-1;
  readln(x,y,w);
  while x<>0 do
    begin
      r[x,y]:=w;
      readln(x,y,w);
    end;
  eet[1]:=0;
  for i:=2 to n do
    begin
    max:=0;
    for j:=1 to n do
      if r[j,i]<>-1 then
        if r[j,i]+eet[j]>max thenmax:=r[j,i]+eet[j];
    eet:=max;
    end;
    et[n]:=eet[n];
    for i:=n-1 downto 1 do
      begin
        min:=10000;
        for j:=1 to n do
         if r[i,j]<>-1 then
           if et[j]-r[i,j]<min then min=et[j]-r[i,j];

      et:=min;

   end;

for i:=1to n-1 do

  ifet=eet then write(i,'->');

      write(n);readln;
end.