关键路径是有向带权无环图的一种寻求路径的算法，采用四组数据，两组点的，两组边的，表格化后一目了然。
分别是：ve(k)，vl(k)，e(i) ，l(i)
点：k表示点的标识
ve：最早发生时间（从初始节点开始，取最大值。（从左到右，取最大））
vl：最迟发生时间 （在ve的基础上，从最后一个节点开始，减去权值，取最小。（从右到左，取最小））
边：i表示边的标识
e：最早开始时间（边对应的出发节点的ve）
l：最迟开始时间 （边对应的终止节点的vl减去变得权值）
再引入一个d的概念，l-e，最终选取d为0的边来串联点，构成关键路径。
在计算出ve后，即可确定关键路径。
松弛时间=l - e
图如下，举例说明
第一步：求ve
ve（k），从起点0出发，权值最长的走法，从前到后。ve（0）=0
ve（1）=3，就是a0
ve（2）=4，就是a1
ve（3）=ve（1）+a2=5，可以这么理解，也可以理解成从0到3，最长路径是0-1-3，权值加起来是3+2=5
ve（4）=max{ve（1）+a3 ， ve（2）+a4} 取较大的值，也可以理解成0-1-4和0-2-4，哪个权值大取哪个。
以此类推……
入度不为1的节点，通过前一节点加上指向该节点的权值取较大值更科学，直接算路径长更直观
第二步：求vl
vl（k），从终点往回倒，减去前一边的权值，取最小。vl（10）=28
vl（9）=vl（10）-a14=22
vl（8）=vl（9）-a13=21
vl（7）=min{vl（9）-a11 ，vl（8）-a12}=11
以此类推……
第三步：求e
最早开始时间，就是边的出发节点的ve
第四步：求l
用边的终止节点的 vl 减去边的权值
a0从0指向1，用vl（1）-a0
l（a0）=vl（1）-a0 = 3
a2从1指向3，用vl（3）-a2
l（a2）=vl（3）-a2=13
以此类推……
通过 l-e 得出d
d为0的边，构成关键路径
即，a1，a4，a8，a12，a13，a14构成关键路径
完成
标签：ve,路径,vl,a0,权值,数据结构,节点,解法 From： https://www.cnblogs.com/kuailest/p/16756721.html