AOE网关键路径的算法，最最最最直接的算法，一学就会

傷城~ 2022-09-25 09:19 176阅读 0赞

# 先了解一下AOE网和关键路径： #

如果在有向图中用顶点表示事件，用弧表示活动，用弧上的权表示活动持续时间，称该带权有向图(即有向网)为边表示活动的网(activity on edge network),简称AOE网。

在AOE网中，只有一个顶点代表的事件发生后，从该顶点出发的各个弧所代表的活动才能开始，只有以弧头关联一个顶点的各个弧所代表的活动都已结束，该顶点所代表的事件才能发生。

一项工程可以由若干个子工程活动组成。用AOV网表示这项工程所关心的是各子工程之间的优先次序，即所得到得拓扑有序序列；而用AOE网表示这项工程所关心的是完成整个工程至少需要多少时间，哪些子工程是影响这项工程进度的关键活动，如何加快整个工程的进度等问题。

由于在AOE网中某些活动可以并行进行，所以完成工程的最短时间是从源点到汇点路径的最大长度(指路径上各活动持续时间之和最大，而不是路径上弧的数目最多)。把从源点到汇点路径长度最大的路径称作关键路径(critical path),关键路径上的活动称作关键活动。关键活动的长度是整个工程的最短工期，加快关键活动的完成是加快工程进度缩短工期地关键。

# 求AOE网关键路径算法的步骤： #

(1) 输入e条弧<Vj,Vk>，建立AOE网的存储结构。

(2) 从源点V1出发，令ve\[1\]=0;按拓扑有序序列次序求其余各顶点的最早发生时间ve\[k\](2<=k<=n)，ve\[k\]=max\{ve\[j\]+dut(<Vj,Vk>)\};如果得到的拓扑有序序列中顶点个数小于网中顶点的个数n，说明网中存在环路，不能求关键路径算法终止，否则执行步骤(3).

(3) 从汇点Vn出发,令vl\[n\]=ve\[n\],按逆拓扑有序序列求其余各顶点的最迟发生时间vl\[k\](n-1>=k>=1),vl\[k\]=min\{vl\[Vj\]-dut(<Vk-Vj>)\}。

(4) 根据各顶点的ve值和vl值，求每条弧的最早开始时间e\[s\]和最迟开始时间l\[s\];e\[s\]等于弧s的弧尾顶点Vk的最早发生时间ve\[k\],而l\[s\]等于弧头顶点Vk的最迟发生时间减去弧s的权值；若某条弧s满足e\[s\]=l\[s\]则为关键活动，由所有关键活动构成的网的一条或几条关键路径。

举一个例子帮助理解：

![Center][]

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

[Center]: /images/20220718/fc67d8fde9b44015953045b75643f718.png
[SouthEast]: /images/20220718/2e541022d5c64654b5c21ea8805b75f2.png
[SouthEast 1]: /images/20220718/923b7b744b10414289cc915d234d13be.png
[SouthEast 2]: /images/20220718/4056efcad5a84c3891f2ed410b6d76c5.png
[SouthEast 3]: /images/20220718/446d8983b5f543be91549d0d8061812f.png