关键路径算法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.
|