aoe网java如何测试,AOE网
AOE网实用场景
主要用在如何计算一个工程的完工时间，和优化工程方案减少工程完工时间。
辅助决策系统，工程管理、生产管理运用非常多。
也就是计算关键路径，也可以说是最长路径。
1、概念
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网。
2、特点
有向无环图
拓扑排序
没有入度的顶点称为始点或源点。
没有出度的顶点称为终点或汇点。
关键路径，就是求最大的路径。
一般是一个开始点，一个结束点。
2、排序算法
算法的结果就是找到关键路径
etv( Time Of ) 事件最早发生时间，顶点最早发生时间。
ltv( Time Of ) 事件最晚发生时间，顶点最晚发生时间。
ete( Time Of Edge) 活动最早开始时间，边最早开始时间。
lte( Time Of Edge) 活动最晚开始时间，边最晚开始时间。
1.png
2.png
3.png
3、代码实现
java.util.;
java.util.List;
/**
* : bobo
* time: 2019/1/11 5:36 PM
* email:
*/
class AOE {
//根据上面的图来定义数组的长度
int = 9;
// etv( Time Of ) 事件最早发生时间，顶点最早发生时间
int[] etv = new int[];
// ltv( Time Of ) 事件最晚发生时间，顶点最晚发生时间
int[] ltv = new int[];
// ete( Time Of Edge) 活动最早开始时间，边最早开始时间
int[] ete = new int[];
// lte( Time Of Edge) 活动最晚开始时间，边最晚开始时间
int[] lte = new int[];
int[] = new int[];
int top2 = 0;
/**
* 拓扑排序算法
* @param 拓扑图数组集
* @
*/
List ([] ) {
int top = 0; //栈顶指针, 对应索引值
int[] stack = new int[];//用来存放入度为0的顶点，数组效率最高，存放顶点的下标索引值
//循环得到入度为0的所有顶点
for (int i = 0; i < .; i++) {
= [i];
if (.in == 0) {
stack[++top] = i;
//开始算法的逻辑
List = new ();
while (top != 0) {
int = stack[top--];
.add((T) [].data);
//保存拓扑序列顺序
[top2++] = ;
//更新当前输出节点所有的出边(后继顶点)
for ( e = [].first; e != null; e = e.next) {
int index = e.index;
//入度减一
[index].in--;
if ([index].in == 0) {
stack[++top] = index;
// 1. 计算顶点的最早开始时间
if(etv[index] < (etv[] + e.)){
etv[index] = etv[] + e.;
;
/**
* 关键路径算法
*/
void ([] ){
// List = ();
//初始化顶点最晚发生时间(ltv)都为汇点时间
for (int i = 0; i < ; i++) {
ltv[i] = etv[ - 1];
//从汇点开始倒过来计算 顶点的最晚开始时间(ltv)
while (top2 > 0) {
int = [--top2];//从汇点开始
for ( e = [].first; e != null; e = e.next) {
int index = e.index;
// 2. 计算顶点的最晚开始时间
if(ltv[index] - e. < ltv[]){
ltv[] = ltv[index] - e.;
//通过 etv 和 ltv 计算出ete 和 lte
for (int i = 0; i < ; i++) {
for ( e = [i].first; e != null; e = e.next) {
int index = e.index;
ete[i] = etv[i];// 3. 边最早的时间 ete，就是顶点最早时间 etv
lte[i] = ltv[index] - e.; // 4. 计算边最晚发生时间，ltv[index]里面已经是选的最小的权重
// if(ete[i]==lte[i]){
// .out.([i].data+" "+[index].data+" "+e.);
// }
/**
* 边表节点
*/
class {
int index; //用来存放顶点的下标索引值
int ; //存放边的权重值
next;
(int index, next) {
this.index = index;
this.next = next;
(int index, int , next) {
this.index = index;
this. = ;
this.next = next;
/**
* 顶点表节点
*/
class {
int in;//入度
T data;
first;
(int in, T data, first) {
this.in = in;
this.data = data;
this.first = first;
5、测试
@Test
void main(){
[] = new [9];
a = new (3, 5, null);
a2 = new (2, 4, a);
a3 = new (1, 6, a2);
[0] = new (0, 1, a3);
b1 = new (4, 1, null);
[1] = new (1, 2, b1);
c1 = new (4, 1, null);
[2] = new (1, 3, c1);
d1 = new (5, 2, null);
[3] = new (1, 4, d1);
e1 = new (7, 5, null);
e2 = new (6, 7, e1);
[4] = new (2, 5, e2);
f2 = new (7, 4, null);
[5] = new (1, 6, f2);
f3 = new (8, 2, null);
[6] = new (1, 7, f3);
f4 = new (8, 4, null);
[7] = new (2, 8, f4);
[8] = new (2, 9, null);
List list = (List) ();
.out.print("拓扑序列：");
for ( : list) {
.out.print( + " ");
.out.();
//打印关键路径
();
.out.print("顶点最早发生时间: ");
for (int i = 0; i < ; i++) {
.out.print(etv[i] + " ");
.out.();
.out.print("顶点最晚发生时间: ");
for (int i = 0; i < ; i++) {
.out.print(ltv[i] + " ");
.out.();
.out.print("边最早发生的时间: ");
for (int i = 0; i < ; i++) {
.out.print(ete[i] + " ");
.out.();
.out.print("边最晚发生的时间: ");
for (int i = 0; i < ; i++) {
.out.print(lte[i] + " ");
.out.();
//打印关键路径
.out.("关键路径: ");
for (int i = 0; i < ; i++) {
for ( e = [i].first; e != null; e = e.next) {
int index = e.index;
ete[i] = etv[i];
lte[i] = ltv[index] - e.;
if(ete[i]==lte[i]){
.out.("V(" + [i].data + ") -> V(" + [index].data + ") -> E(" + e. + ")");
6、结果
拓扑序列：1 4 6 3 2 5 8 7 9
顶点最早发生时间: 0 6 4 5 7 7 14 12 16
顶点最晚发生时间: 0 6 6 6 7 8 14 12 16
边最早发生的时间: 0 6 4 5 7 7 14 12 0
边最晚发生的时间: 1 6 6 6 7 8 14 12 0
关键路径:
V(1) -> V(2) -> E(6)
V(2) -> V(5) -> E(1)
V(5) -> V(7) -> E(7)
V(5) -> V(8) -> E(5)
V(7) -> V(9) -> E(2)
V(8) -> V(9) -> E(4)
