数据结构里关键路径上的事件最早发生时间与最晚发生时间是否相同

Question

因为做题发现不是关键路径上的事件最早与最晚是不同的，而试卷上的答案是关键路径上事件最早于最晚是一样的

Answer 1

不同。

事件最早发生时间ve（earliest time of vertex）：顶点vk的最早发生时间，从始点到vi的最长（加权）路径长度。

事件最晚发生时间vl(lastest time of vertex)：顶点vk的最晚发生时间，在不拖延整个工期的条件下，vi的可能的最晚发生时间。

A、从开始顶点 v1 出发，令 ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。 

Ve(k)=max{ve(j)+dut(<j,k>)} , j ∈ T 。其中T是以顶点vk为尾的所有弧的头顶点的集合（2 ≤ k ≤ n）。

如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

B、从完成顶点

出发，令

，按逆拓扑有序求其余各顶点的允许的最晚发生时间：

vl(j)=min{vl(k)-dut(<j,k>)} ,k ∈ S 。其中 S 是以顶点vj是头的所有弧的尾顶点集合（1 ≤ j ≤ n-1）。

扩展资料：

优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。

EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。

参考资料来源：百度百科-关键路径

Answer 2

关键路上的最早发生时间和最晚发生时间一定相同。
这就是寻找关键路径的办法 啊
第一步：拓扑排序、
第二步： 依照排序顺序从前往后计算事件（即结点代表事件）发生的最早时间
第三步： 在以逆拓扑顺序计算事件（即结点代表事件）发生的最早时间
第四步：根据求出的时间最早最晚发生事件 计算每条活动上的（图的边代表活动）最早 最晚时间
第五步：若活动的最早时间最晚时间相同 则把它纳入关键路径本回答被网友采纳

Answer 3

楼上的回答可能没有完全理解楼主的意思。说一个肯定对的结论，如果事件的最早发生时间等于最晚发生时间，那么满足这个条件的顶点等价于该顶点在关键路径上。如果一个弧的两个邻接顶点都满足最早发生时间等于最晚发生时间，只能说这两个顶点都在在关键路径上，但是并不能确定这个弧所对应的活动就是关键活动。全是文字描述看起来可能有点累(๑˙ー˙๑)