AOE 有向无环网 关键路径 算法

1. 相关概念:

1. 有向无环网(Activity On Edge Network,简写为AOE)

1. 用顶点表示事件, 弧表示活动, 边上权值表示活动的消耗时间
   1. AOE与AOV网的比较: AOV网的边+权值=AOE网

2. 始点, 源点:

AOE网中,没有入边的顶点

3. 终点, 汇点:

AOE网中, 没有出边的顶点

4. AOE网中事件发生的条件:

入度活动都得执行完, 该事件具备发生的条件

5. 事件最早发生时间:

即刚好全部前提活动都执行完的时间, 取决于最长的前提路径

6. 事件最晚发生时间:

如果该事件晚于该事件, 则会延误整个工期, 取决于==到终点的最短路径==

7. 活动的最早发生时间:

由弧尾最早发生时间决定

8. 活动最晚发生时间:

1. 该活动不能更晚发生的时间点, 否则将延误整个工期
2. 由弧头顶点的最晚时间和该活动所花费时间决定

9. 关键弧

最早和最晚时间相同的弧, 即该活动必须立刻执行, 否则将会延误整个工期

2. 算法思想:

1. 求出所有关键弧, 以此拼凑出关键路径
   1. 关键弧判定条件: 最早发生时间=最晚发生时间
      1. 分别根据弧头和弧尾求出两个时间

3. 在C语言中的实现

梗概:

1. 用拓扑顺序来求每个顶点的最早发生时间
   1. 并由此得到反拓扑序列
2. 用反拓扑顺序来求每个顶点的最晚发生时间
3. 遍历每条弧, 找出所有关键弧
   1. 根据顶点两个时间求出弧的两个对应时间
   2. 弧的两个时间相等, 则该弧为关键弧 代码:

int vEinTopoOrder(AdjList *G,int* T,int *vE){
//有环返回0,无环返回1
    /*存储*/
    ArcNode *e;
    int i, k, gettop;
    int top=0;
    int count=0;
    int *stack,*indegree;
    indegree=(int*)calloc(G->vexnum,sizeof(int));
    stack=(int*)calloc(G->vexnum,sizeof(int));
    vE=(int*)calloc(G->vexnum,sizeof(int));
    T=(int*)calloc(G->vexnum,sizeof(int));
    int top_T=0;
    /*统计所有顶点的入度*/
    for(i=0;i<G->vexnum;++i)
        indegree[i]=0;
    for(i=0;i<G->vexnum;++i){
        e=G->vertex[i].firstarc;
        for(;e;){
            ++indegree[e->adjvex];
            e=e->nextarc;
        }
    }
    for(i=0;i<G->vexnum;++i)
        vE[i]=0;
    /*把所有入度为0的顶点都入栈*/
    for(i=0;i<G->vexnum;++i)
        if(!(indegree[i]))
            stack[++top]=i;
    for(;top;){
        /*获得拓扑顺序*/
        gettop=stack[top--];
        /*获取反拓扑序列*/
        T[++top_T]=gettop;
        count++;
        /*遍历出度顶点*/
        for(e=G->vertex[gettop].firstarc;e;){
            k=e->adjvex;
            /*删除入度,并判断删除后入度是否可以进栈*/
            if(!(--indegree[k]))
                stack[++top]=k;
            /*取最长的路径作顶点最早时间*/
            if(vE[gettop]+e->info > vE[k])
                vE[k]=vE[gettop]+e->info;
            e=e->nextarc;
        }
    }
    free(indegree);
    free(stack);
    /*如果有环,就会有顶点没有排序到*/
    return!(count<G->vexnum);
}
 
int CriticalPath(AdjList *G){
    ArcNode *e;
    int i,tail,head,costT,edgeE,edgeL,top; char tag;
    int *vL=(int*)calloc(G->arcnum,sizeof(int));
    int *T,*vE;
    /*获取所有顶点最早发生时间vE,并获取反拓扑序列*/
    if(!vEinTopoOrder(G,T,vE))return 0;
    /*初始化顶点时间与最早时间相等*/
    for(i=0;i<G->vexnum;++i)
        vL[i]=vE[G->vexnum-1];
    /*遍历反拓扑序列来求vL*/
    for(;top;){
        tail=T[top--];
        e=G->vertex->firstarc;
        /*遍历所有出度弧*/
        for(;e;){
            head=e->adjvex;costT=e->info;
            /*取最短反路径为顶点最晚时间*/
            if(vL[head]-costT < vL[tail])
                vL[tail]=vL[head]-costT;
            e=e->nextarc;
        }
    }
    /*遍历所有弧,以找出所有关键弧*/
    for(tail=0;tail < G->vexnum;++tail){
        e=G->vertex[tail].firstarc;
        for(;e;){
            head=e->adjvex; costT=e->info;
            /*根据顶点最晚和最早时间求弧的对应时间*/
            edgeE=vE[tail]; edgeL=vL[head]-costT;
            /*两个时间相等说明该弧为关键路径之一*/
            tag=(edgeE==edgeL)?'*':' ';
            /*打印关键路径中的一部分*/
            printf("%c,%c,%d,%d,%d,%c\n",G->vertex[tail].data,
            G->vertex[head].data,costT,edgeE,edgeL,tag);
            e=e->nextarc;
        }
    }
    free(vL);
    free(T);
    free(vE);
    return 1;
}