设有一个工程网络如下图表示(无环路的有向图)：
其中，顶点表示活动，①表示工程开始，⑤表示工程结束(可变，用N表示)，边上的数字表示活动延续的时间。
如上图中，活动①开始5天后活动②才能开始工作，而活动③则要等①、②完成之后才能开始，即最早也要7天后才能工作。
在工程网络中，延续时间最长的路径称为关键路径。上图中的关键路径为：①—②—③—④—⑤共18天完成。
关键路径的算法如下：
1.数据结构：
R[1..N，1..N]OF INTEGER； 表示活动的延续时间，若无连线，则用-1表示；
EET[1..N] 表示活动最早可以开始的时间
ET[1..N] 表示活动最迟应该开始的时间
关键路径通过点J，具有如下的性质：EET[J]=ET[J]
2.约定：
结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动。
程序清单：
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)；{输入从活动X到活动Y的延续时间，以0为结束}
WHILE X<>0 DO
BEGIN
R[X，Y]:=W； 1
END；
EET[1]：=0；{认为工程从0天开始}
FOR I：=2 TO N DO
BEGIN
MAX:=0；
FOR J:=1 TO N DO
IF R[J，I]<>-1 THEN
IF 2 THEN MAX:=R[J，I]+EET[J]；
EET[I]:=MAX；
END；
3
FOR I：=N-1 DOWNTO 1 DO
BEGIN
MIN：=10000；
FOR J：=1 TO N DO
IF R[I，J]<>-1 THEN
IF 4 THEN MIN：=ET[J] - R[I，J]；
ET[I]：=MIN；
END；
WRITELN(EET[N])；
FOR I：=1 TO N -1 DO
IF 5 THEN WRITE(I，'→')；
WRITE(N)；READLN
END. 
