aoe时间

图论算法之AOE⽹

前⾔

AOE⽹主要⽤在如何计算⼀个⼯程的完⼯时间，和优化⼯程⽅案减少⼯程完⼯时间；在实际开发过程中，会⽤到很多，作为现代管理中很重

要的⼀部分，⽽aoe⽹的核⼼点在于如何求关键路径，这在本篇⽂章中会⼤量讲述

aoe⽹概念

在⼀个表⽰⼯程的带权有向图中，⽤顶点表⽰事件，⽤有向边表⽰活动，⽤边上的权值表⽰活动的持续时间，这种有向图的边表⽰活动的

⽹，我们称之为AOE⽹。没有⼊度的顶点称为始点或源点

没有出度的顶点称为终点或汇点

如下图开始，构造⼀个aov⽹

从开始组装，到分别去造不同的零件，最后到组装完成，描述了⼯程的先后顺序，利⽤拓扑排序则能快速找到路径；但现实的⼯程，肯定

有时间快慢之分，⼀定会有权重

这样选择出最上的⽣产时间就是5.5天，并且不可能发动机还没⽣产完就集中；要做优化就⼀定在发动机的⽣产优化，能优化出⼀些时间。

关键路径查找

从源点开始，汇点或终点结束

在aoe⽹中⼀般只有⼀个开始点和⼀个终点结束。

上图所展⽰的情况，这是⼀个连续的过程，权重则表⽰所需时间，⽽每个顶点展⽰的是⼀个事件活动。并且aoe⽹⼀般只有⼀个开始点和

⼀个汇点；找到最长路径以下⾯红⾊表⽰

如果其中⼀条关键路径被优化了，这个关键路径就有可能变化了。

etv(EarliestTimeOfVertex)事件最早发⽣时间，顶点最早发⽣时间

ltv(LatestTimeOfVertex)事件最晚发⽣时间，顶点最晚发⽣时间

结合下⾯的图来就是

上⾯的顶点这样去理解，2的最早发⽣时间结合图看就是6开始，⽽5号则为7，因为⼀定要等第⼀件事情做完了才能发⽣第⼆件事情；3

事件的发⽣就多了2个休息的事件单位。⼀定是需要等待触发。事件触发。⼀定要等待最长的做完了才能做后⾯的。⽽计算机则是由后往

前推。不管从哪⾥推。起点⼀定是0.

找到这个时间只要找到相等得路径就

是关键路径得顶点

ete(EarliestTimeOfEdge)活动最早开始时间，边最早开始时间

lte(LatestTimeOfEdge)活动最晚开始时间，边最晚开始时间

从1到3得时候，这个路径时间，其实可以改变，也就是说我们可以先等待两个⼩时在开始⼯作都⾏，都可以开始做事情。可以选择得。我

们要考虑得是最早开始做得事件的时间，和最晚做事件的时间。

有顶点还需要去算表，是通过邻接表表⽰

代码实现

建⽴节点

/**

*边表结点

*/

classEdgeNode{

intdata;

intweight;

EdgeNodenext;

publicEdgeNode(intdata,intweight,EdgeNodenext){

=data;

=weight;

=next;

}

publicEdgeNode(intdata,EdgeNodenext){

=data;

=next;

}

}

/**

*顶点表结点

*/

classVertexNode{

intin;//⼊度

intdata;

EdgeNodefirst;

publicVertexNode(intin,intdata,EdgeNodefirst){

=in;

=data;

=first;

}

}

然后需要把etvltvetelte都要计算出来

//etv(EarliestTimeOfVertex)事件最早发⽣时间，顶点最早发⽣时间

int[]etv=newint[9];

//ltv(LatestTimeOfVertex)事件最晚发⽣时间，顶点最晚发⽣时间

int[]ltv=newint[9];

//ete(EarliestTimeOfEdge)活动最早开始时间，边最早开始时间

int[]ete=newint[9];

//lte(LatestTimeOfEdge)活动最晚开始时间，边最晚开始时间

int[]lte=newint[9];

代码是从aov⽹中变化⽽得到

需要做保存得栈和指针计算

int[]stack2=newint[9];

inttop2=0;

进⾏拓扑排序。拓扑排序计算出顶点

/**

*拓扑排序

*/

publicvoidtopologicalSort(){

inttop=0;//栈顶指针

int[]stack=newint[9];//⽤来存放⼊度为0的顶点

//循环得到⼊度为0的所有顶点

for(inti=0;i<;i++){

if(graphAdjList[i].in==0){

stack[++top]=i;

}

}

//开始算法的逻辑

while(top!=0){

intgetTop=stack[top--];//出栈⼀个

//(""+graphAdjList[getTop].data);

//保存拓扑序列顺序

stack2[top2++]=getTop;

//更新当前输出节点所有的出边（后继顶点）

for(EdgeNodee=graphAdjList[getTop].first;e!=null;e=){

intk=;

//⼊度减⼀

graphAdjList[k].in--;

if(graphAdjList[k].in==0){

stack[++top]=k;

}

//计算顶点的最早开始时间

if((etv[getTop]+)>etv[k]){

etv[k]=etv[getTop]+;

}

}

}

}

从0开始往后找。不断得进⾏⽐较⼤⼩；

//计算顶点的最早开始时间

if((etv[getTop]+)>etv[k]){

etv[k]=etv[getTop]+;

}

最晚发⽣时间，取节点得最⼩发⽣时间，⼩的进⾏覆盖。

//初始化ltv都为汇点时间

for(inti=0;i<9;i++){

ltv[i]=etv[8];

}

这是从后往前推，不断判断是否⼩于；顶点得最晚发⽣时间就能计算出来。

//从汇点开始倒过来计算ltv

while(top2>0){

intgetTop=stack2[--top2];//从汇点开始

for(EdgeNodee=graphAdjList[getTop].first;e!=null;e=){

intk=;

if(ltv[k]-

ltv[getTop]=ltv[k]-;

}

}

}

在计算关键路径时，已经是关键路径，其他得边不⽤存储。选择最短得路径。也是从后继节点出度。ete[i]=etv[i];最早开始时间。etv[k];

etv从后往前推。

//通过etv和ltv计算出ete和lte

for(inti=0;i<9;i++){

for(EdgeNodee=graphAdjList[i].first;e!=null;e=){

intk=;

ete[i]=etv[i];//边的最早时间，就是顶点的最早时间

lte[i]=ltv[k]-;//ltv[k]⾥⾯已经是选的最⼩的权重

if(ete[i]==lte[i]){

n(graphAdjList[i].data+""+graphAdjList[k].data+""+);

}

}

}

总结

整篇⽂章对aoe算法查找最短路径做了个⽅法及代码实现做了思路解析，如果要深⼊理解，还需要更⼀步⾃⼰实现⼀下