图的应用——关键路径
AOE 网
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称 AOE 网。AOE 网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。
AOE 网的性质
只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。
AOE 网所能解决的问题
完成整个工程至少需要多少时间?
为缩短完成工程所需的时间, 应当加快哪些活动?
关键路径
关键路径长度是整个工程所需的最短工期。
关键路径：在 AOE 网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
关键活动：关键路径上的活动称为关键活动。
术语
源点：表示整个工程的开始点，也称起点
收点：表示整个工程的结束点，也称汇点
事件结点：单位时间，表示的是时刻
活动（有向边）：它的权值定义为活动进行所需要的时间。方向表示起始结点事件先发生，而终止结点事件才能发生
事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件最早能够发生的时刻
事件的最迟发生时间（V l (j)）：不影响工程的如期完工，本结点事件必须发发生的时刻
活动的最早开始时间：e( ai ) = Ve( j )
活动的最迟开始时间：l( ai ) = V l( k ) - dut( j , k )
事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件最早能够发生的时刻
事件的最迟发生时间（V l (j)）：不影响工程的如期完工，本结点事件必须发发生的时刻
活动的最早开始时间：e(ai ) = Ve( j )
活动的最迟开始时间： l (ai ) = V l( k ) - dut( j , k )
关键活动：最早开始时间 ＝ 最迟开始时间的活动
关键路径：从源点到收点的最长的一条路径，或者全部由关键活动构成的路径
算法设计
事件(顶点) 的 最早发生时间 ve(j)ve(j) = 从源点到顶点 j 的最长路径长度
ve(源点) = 0
ve(j) = Max{ve(i) + dut(<i, j>)} (<i, j>∈T)T 是所有以第 j 个顶点为弧头的弧的集合
事件(顶点) 的 最迟发生时间 vl(k)vl(k) = 从顶点 k 到汇点的最短路径长度
vl(汇点) = ve(汇点)
vl(i) = Min{vl(j) – dut(<i, j>)} (<i, j>∈S)S 是所有以第 i 个顶点为弧尾的弧的集合
假设第 i 条弧为 <j, k>, 则 对第 i 项活动言:
活动(弧)”的 最早开始时间 e(i)e(i) = ve(j)
活动(弧)的 最迟开始时间 l(i)l(i) = vl(k) – dut(<j,k>)
算法要点
求 ve 的顺序应该是按拓扑有序的次序
求 vl 的顺序应该是按拓扑逆序的次序
拓扑逆序序列即为拓扑有序序列的逆序列，应该在拓扑排序的过程中，另设一个 “栈” 记下拓扑有序序列
算法实现
版权声明: 本文为 InfoQ 作者【若尘】的原创文章。
原文链接:【http://xie.infoq.cn/article/e6ccbb31633483f88ef040d8c】。文章转载请联系作者。
还未添加个人签名 2021.01.11 加入
还未添加个人简介
评论