数据结构-关键路径

tech2022-08-01  159

AOV、AOE都是有权无向图,AOV边不带权值,AOE带权值。

关键路径是AOE中,开始顶点到结束顶点的所有路径中,具有最大路径长度的路径成为关键路径,路径上的点是关键活动。

(1)关键路径如果有多条,至提高一条关键路径上的关键活动并不能缩短工期,必须要加快所有关键路径上的关键活动才能加快工期。

(2)关键路径只有一条,关键活动也不是无限制缩短,工期会无限缩短的,因为可能缩到一定程度,这个节点就不是关键活动了。

求解关键路径的主要步骤:

(1)求解ve(),求解每个节点(事件)的最早发生时间: 规定ve(0) = 0。 ve(n) = max(ve(n-1)+x1,ve(n-2)+x2) 能够到达n的所有路径中最大值。

(2)求解vl(),求解每个节点(事件)的最迟发生时间:规定vl(终点)= ve(终点)。vl=min(vl(n-1)-x1,vl(n-2)-x2) 能够返回n的所有路径中的最小值。

(3)求解e(),求解每个活动的最早开始时间。->活动a连接的两端的顶点的最早发生时间

(4)求解l(),求解每个活动的最迟开始时间。->活动a连接的两端的终点的最迟发生时间-活动a历经的时间。

(5)用e()-l(),找出等于0的点,等于0的路径就是关键路径。

关键路径为:a2,a5,a7. v1->v3->v5->v6

               

20题。无需将所有步骤都完成,因为可以直接看出。最终选择C

                     

21 ,求解ve(),vl() e() l () ,将e() - l () = 0 可以看出所有关键路径。因此有三条,最终选择C。

              

最新回复(0)