面是三个关于有向图运算的叙述()
(1) 求有向图结点的拓扑序列,其结果必定是唯一的
(2) 求两个指向结点间的最短路径,其结果必定是唯一的
(3) 求AOE网的关键路径,其结果必定是唯一的
其中哪个是正确的?
首先,在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径为关键路径。
计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。
先来看看四个特征属性的含义:
Ø Ve(j):是指从始点开始到顶点Vk的最大路径长度
计算技巧:
(1)从前向后,取大值:直接前驱结点的Ve(j)+到达边(指向顶点的边)的权值,有多个值的取较大者
(2)首结点Ve(j)已知,为0
Ø Vl(j):在不推迟整个工期的前提下,事件vk允许的最晚发生时间
计算技巧:
(1)从后向前,取小值:直接后继结点的Vl(j) –发出边(从顶点发出的边)的权值,有多个值的取较小者;
(2)终结点Vl(j)已知,等于它的Ve(j))