Question

图的关键路径

Answer 1

关键概念定义

AOV网 ：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，就是AOV网。

关键路径算法原理 ：先求所有顶点的事件最早发生时间（从起点开始计算），如有顶点1和顶点2都到达顶点3，那么顶点3的最早开始时间为max(顶点1 + 路径长度，顶点2 + 路径长度)；之后求出所有顶点的时间最迟发生时间（从终点开始计算），如顶点3会到达顶点4和顶点5，那么顶点3的最迟发生时间为min（顶点4 - 路径长度，顶点5 - 路径长度)。比较事件最早发生时间数组和事件最迟发生时间数据，若是对应位置的值相等（即没有可延迟的时间），那么该顶点就是关键路径上的顶点。比较完所有顶点即可输出关键路径。