首页 > 试题广场 >

求关键路径 设有一个工程网络如下图表示(无环路的有向图):

[填空题]
求关键路径
设有一个工程网络如下图表示(无环路的有向图):
其中,顶点表示活动,①表示工程开始,⑤表示工程结束(可变,用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.

这道题你会答吗?花几分钟告诉大家答案吧!