关键路径及其算法

关键路径及其算法

1.关键路径:

在AOE网中所关心的问题是完成整个工程至少需要多少时间和哪些活动是影响整个工程进度的关键。

由于AOE网中的某些活动能够平行地进行，故完成整个工程所需的时间是从开始顶点到结束顶点的最长路径长度（路径上的权值和）最长路径叫关键路径。如上述工程的关键路径是1->4->3->2,关键路径长度为2+7+6=15，关键活动是a2，a4，a5。

2.关键路径算法1:

  1)将网拓扑排序

  2)以拓扑序列划分阶段

  3)用动态规划求解关键路径

程序如下：

program gjlu;
const maxn=10;
var
map:array[1..maxn,1..maxn] of integer;
a:array[1..maxn] of 0..maxn;
b:array[1..maxn] of integer;
c:array[1..maxn] of 0..maxn;
n:integer;
procedure init;
var i,j:integer;
begin
readln(n);
for i:=1 to n do
  for j:=1 to n do
   read(map[i,j]);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
end;
function tporder:boolean;
var i,j,k:integer;
into:array[1..maxn] of byte;
begin
tporder:=false;
fillchar(into,sizeof(into),0);
  for i:=1 to n do
   for j:=1 to n do
    if map[i,j]>0 then inc(into[j]);
for i:=1 to n do
  begin
   j:=1;
   while (j<=n)and(into[j]<>0) do inc(j);
   if j>n then exit;
   a:=j;
   into[j]:=$ff;
   for k:=1 to n do
    if map[j,k]>0 then dec(into[k]);
end;
tporder:=true;
end;
procedure calc;
var i,j:integer;
begin
b[a[1]]:=0;c[a[1]]:=0;
for i:=2 to n do
  for j:= 1 to i-1 do
   if b[a[j]]+map[a[j],a]>b[a] then
    begin b[a]:=b[a[j]]+map[a[j],a];c[a]:=a[j]; end;
end;
procedure print;
var i,j,k:integer;
d:array[1..maxn] of 0..maxn;
begin
writeln('long=',b[a[n]]);
k:=c[a[n]];i:=0;
while k<>0 do
  begin i:=i+1;d:=k;k:=c[k] end;
for j:=i downto 1 do
write(d[j],'  ');
writeln(a[n])
end;
begin
init;
if tporder then
  begin
   calc;
   print;
  end;
end.