AOE网 无环赋权有向图：顶点表示事件，弧表示活动

关键活动按时开始和完成，不会影响整个工程的进度。

只有缩短关键活动的完成时间才有可能缩短整个工程完成时间。

非关键活动，即使缩短完成时长也不一定能缩短整个工程完成时间。

关键路径（不一定唯一，但长度相等）：源点到终点的最长路径

关键活动：关键路径上的活动

事件vj的最早发生时间ve(j)、事件vi的最迟发生时间vl(i)

ve(j)：从源点v0到vj的最长路径的长度。

vj一旦发生，以vj为起点的各条出边<vj,vk>所表示活动aj可以开始，即ve(j)=ae(j)

vl(i)：从终点vn-1开始计算。vl(n-1)=ve(n-1)。vl(i)为其(后继事件的最迟发生时间减去各个vi到vj路径上的活动时长)的最小值

该图中vl(1)=6，表格中有错应做修改

活动<i,j>的最早开始时间ae(<i,j>)、最迟开始时间al(<i,j>)

活动<i,j>的最早开始时间=事件vi的最早发生时间

活动<i,j>的最迟开始时间=事件vj的最迟发生时间-活动<i,j>的时长

该图中，活动名称a1...a11应改为a0...a10

ae(<i,j>)=al(<i,j>)的活动为关键活动。

AOV网：

顶点活动（Activity On Vertex，AOV）网是指用顶点表示活动，而用边集表示活动间优先关系的有向图。例如图10-57的先导课程示意图就是AOV网，其中图的顶点表示各项课程，也就是“活动”；有向边表示课程的先导关系，也就是“活动间的优先关系”。显然，图中不应当存在有向环，否则会让优先关系出现逻辑错误。

AOE网：

 

边活动（Activity On Edge，AOE）网是指用带权的边集表示活动，而用顶点表示事件的有向图，其中边权表示完成活动需要的时间。例如图10-59中，边a1~a6表示需要学习的课程，也就是“活动”，边权表示课程学习需要消耗的时间；顶点V1~V6。表示到此刻为止前面的课程已经学完，后面的课程可以开始学习，也就是“事件”（如V5表示a4计算方法和a3实变函数已经学完，a6泛函分析可以开始学习。从另一个角度来看，a6只有当a4和a5都完成时才能开始进行，因此当a4计算方法学习完毕后必须等待a5实变函数学习完成后才能进入到a6泛函分析的学习），显然“事件”仅代表一个中介状态。

源点：在AOE网中，没有入边的顶点称为源点；如顶点V1

 

终点：在AOE网中，没有出边的顶点称为终点；如顶点V6

 

AOE网的性质：

·只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；

·只有在某顶点所代表的事件发生后，从该顶点出发的各活动才开始；

AOE网中的最长路径被称为关键路径（强调：关键路径就是AOE网的最长路径），而把关键路径上的活动称为关键活动，显然关键活动会影响整个工程的进度。

关键概念：

1.事件的最早发生时间ve[k]（earliest time of vertex）：即顶点vk的最早发生时间。

从源点向终点方向计算

ve[0] = 0

ve[1] = ve[0] + a0 = 0 + 4 = 4

ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6

ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10

 

2.事件的最晚发生时间vl[k]（latest time of vertex）：即顶点vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。

从终点向源点方向计算

vl[3] = ve[3] = 10

vl[2] = vl[3] - a3 = 10 - 4 = 6

vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4//之所以求最小，保证其他的点的最晚发生时间

vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0 

 

3.活动的最早开工时间e[k]（earliest time of edge）：即弧ax的最早发生时间。

5条边，5个活动

e[0] = ve[0] = 0

e[1] = ve[0] = 0

e[2] = ve[1] = 4

e[3] = ve[2] = 6

e[4] = ve[1] = 4

 

4.活动的最晚开工时间l[k]（latest time of edge）：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。

e[0] = v[1] - a0 = 4 - 4 = 0

e[1] = vl[2] - a1 = 6 - 3 = 3

e[2] = vl[2] - a2 = 6 - 2 = 4

e[3] = vl[3] - a3 = 10 - 4 = 6

e[4] = vl[3] - a4 = 10 - 6 = 4

 

活动的最早开始时间和最晚开始时间相等，则说明该活动时属于关键路径上的活动，即关键活动

算法设计：

关键路径算法是一种典型的动态规划法，设图G=(V, E)是个AOE网，结点编号为1,2,...,n，其中结点1与n 分别为始点和终点，ak=<i, j>∈E是G的一个活动。算法关键是确定活动的最早发生时间ve[k]和最晚发生时间vl[k]，进而获取顶点的最早开始时间e[k]和最晚开始时间l[k]。

根据前面给出的定义，可推出活动的最早及最晚发生时间的计算方法：

e(k) = ve(i)

l(k) = vl(j) - len(i,j)

结点的最早发生时间的计算，需按拓扑次序递推：

ve(1) = 0

ve(j) = MAX{ etv(i)+len(i, j) }

 

对所有<i,j> ∈E的i  结点的最晚发生时间的计算，需按逆拓扑次序递推：

vl(n) = ve(n)

vl(i) = MIN{vl(j) - len(i, j)} 对所有<i,j>∈E的j

 

这种计算方法， 依赖于拓扑排序， 即计算ve( j) 前，应已求得j 的各前趋结点的ve值，而计算vl(i)前，应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边<i,j>（即入度减1）的同时，执行

if ( ve[i]+len(i,j)) > ve[j] )

ve[j] = ve[i] + len(i,j)

 

这时会发现，如果想要获得ve[j]的正确值，ve[il]~ve[ik]必须已经得到。有什么办法能够在访问某个结点时保证它的前驱结点都已经访问完毕呢？没错，使用拓扑排序就可以办到。

当按照拓扑序列计算ve数组时，总是能保证计算ve[i]的时候ve[il]~ve[ik]都已经得到。但是这时又碰到另一个问题，通过前驱结点去寻找所有后继结点很容易，但是通过后继结点V；去寻找它的前驱结点V1~Vx似乎没有那么直观。一个比较好的办法是，在拓扑排序访问到某个结点时，不是让它去找前驱结点来更新ve[i]，而是使用ve[i]去更新其所有后继结点的ve值。通过这个方法，可以让拓扑排序访问到V；的时候，V1~Vk一定都已经用来更新过ve[i]，此时的ve[i]便是正确值，就可以用它去更新V；的所有后继结点的ve值。

//拓扑序列

stack<int>topOrder;

//拓扑排序，顺便求ve数组

bool topologicalSort()

{

    queue<int>q;

    for(int i=0;i<n;i++)

        if(inDegree[i]==0)

            q.push(i);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        topOrder.push(u);//将u加入拓扑序列

        for(int i=0;i<G[u].size();i++)

        {

            int v=G[u][i].v;//u的i号后继结点编号为v

            inDegree[v]--;

            if(inpegree[v]==0)

                q.push(v);

            //用ve[u]来更新u的所有后继结点

            if(ve[u]+G[u][i].w> ve[v])

                ve[v]=ve[u]+G[u][i].w;

        }

    }

    if(toporder.size()== n)

        return true;

    else

        return false;

}

同理，如图10-64所示，从事件V出发通过相应的活动ar1~ark可以到达k个事件V1~Vk，活动的边权为length[r1]~length[rk]。假设已经算好了事件V1~Vk的最迟发生时间xl[j1]～vl[jk]，那么事件Vi的最迟发生时间就是vl[j1]-length[r1]~vl[jk]-length[rk]中的最小值。此处取最小值是因为必须保证Vj1~Vjk的最迟发生时间能被满足；可以通过下面这个公式辅助理解。

 和ve数组类似，如果需要算出vl[i]的正确值，vl[j1]~vl[jk]必须已经得到。这个要求与ve数组的刚好相反，也就是需要在访问某个结点时保证它的后继结点都已经访问完毕，而这可以通过使用逆拓扑序列来实现。幸运的是，不必再做一次逆拓扑排序来得到逆拓扑序列，而是可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。此时会发现，在上面实现拓扑排序的过程中使用了栈来存储拓扑序列，那么只需要按顺序出栈就是逆拓扑序列。而当访问逆拓扑序列中的每个事件Vi时，就可以遍历Vi的所有后继结点Vj1~Vjk，使用vI[j1]~vl[jk]来求出vl[i]。

这部分的代码如下所示：

fill(vl，v1+n，ve[n-1]);//v1数组初始化，初始值为终点的ve值

//直接使用toporder出栈即为逆拓扑序列，求解v1数组

while(！topOrder.empty())

{

    int u=topOrder.top();//栈顶元素为u

    topOrder.pop();

    for(int i=0;i<G[u].size();i++)

    {

        int v=G[u][i].v;//u的后继结点v

        //用u的所有后继结点v的v1值来更新v1[u]

        if(vl[v]-G[u][i].w < vl[u])

            vl[u]=vl[v]-G[u][i].w;

    }

}

        通过上面的步骤已经把求解关键活动的过程倒着推导了一遍，下面给出上面过程的步骤总结，即“先求点，再夹边”：

①按拓扑序和逆拓扑序分别计算各顶点（事件）的最早发生时间和最迟发生时间：

②用上面的结果计算各边（活动）的最早开始时间和最迟开始时间：

③e[i-→] = l[i-→i]的活动即为关键活动。

主体部分代码如下（适用汇点确定且唯一的情况，以n-1号顶点为汇点为例）：【主体代码】

求取关键路径：

//遍历邻接表的所有边，计算活动的最早开始时间e和最迟开始时间1

for(int u=0；u<n；u++)

{

    for(int i=0；i<G[u].size()；i++)

    {

        int v=G[u][i].v，w=G[u][i].w；

        //活动的最早开始时间e和最迟开始时间1

        int e=ve[u]，l=vl[v]-w；

        //如果e==1，说明活动u->v是关键活动

        if(e==1)

        printf("%d->%d\n"，u,v)；//输出关键活动}

    }

    return ve[n-1]；//返回关键路径长度

}

 

 

在上述代码中，没有将活动的最早开始时间e和最迟开始时间l存储下来，这是因为一般来说e和l只是用来判断当前活动是否是关键活动，没有必要单独存下来。如果确实想要将它存储下来，只需要在结构体Node中添加域e和1即可。

如果事先不知道汇点编号，有没有办法比较快地获得关键路径长度呢？当然是有办法的，那就是取ve数组的最大值。原因在于，ve数组的含义是事件的最早开始时间，因此所有事件中ve最大的一定是最后一个（或多个）事件，也就是汇点。于是只需要在fill函数之前添加一小段语句，然后改变下vl函数初始值即可，代码如下：

int maxLength = 0;

for(int i=0; i<n; ++i)

{

    if(ve[i] > maxLength)

        maxLength = ve[i];

}

fill(vl, vl + n, maxLength);

 

拓扑排序以及求解关键路径都是属于有向无环网的应用

---

拓扑排序:解决工程能否顺序进行的问题

介绍2个概念

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网。

1. 弧表示活动之间的某种制约关系：比如演职人员确定了，场地联系好了，才可以开始进场拍摄。
2. AOV网中不能存在回路，即不能存在环，否则某个活动的开始要以自己完成作为先决条件，这是不现实的

拓扑序列：

设G=（V，E）是一个具有n个顶点的有向图，中的顶点序列~，满足若从顶点到有一条路径，则在顶点序列中顶点必定在之前，则我们称这样的顶点序列为一个拓扑序列

---

拓扑排序：对一个有向图构造拓扑序列的过程。

如果此网的全部顶点都被输出，则说明它是不存在环或回路的AOV网；

如果输出的顶点数少于总共的顶点数，则说明这个网存在环或回路，不是AOV网；

拓扑排序算法：

基本思路：

从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并且删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AVO中不存在入度为0的顶点为止。

确定使用的数据结构：由于需要删除顶点和边，所以用邻接表比较方便

typedef struct EdgeNode
{
    int adjvex;
    int weight;
    struct EdgeNode *node;
}EdgeNode;//边结点(带有权值)
typedef struct VertexNode
{
    int in;//该顶点入度
    int data;//顶点域
    EdgeNode *firstedge;//边表头指针
}VertexNode,AdjList[MAXVEX];//顶点表结点
typedef struct
{
    AdjList adjList;
    int numVertexes,numEdges;//当前图的顶点数和边数
}graphAdjList,*GraphAdjList;

看代码：

//这里使用栈存储入度为0的顶点，避免每个查找都要遍历顶点表找有没有入度为0的顶点
Status TopologicalSort(GraphAdjList G)
{
    EdgeNode *e;
    int count=0;//统计输出顶点个数
    int top=0;//栈指针下标
    int *stack;
    stack=(int*)malloc(G->numVertexes*sizeof(int));
    for(int i=0;i<G->numVertexes;i++)
        if(G->adjList[i].in==0)
            stack[++top]=i;//将入度为0的顶点入栈
    while(top!=0)//top!=0说明栈非空，存在入度为0的顶点
    {
        int gettop=stack[top--];
        print("%d --> ",G->adjList[gettop].data);
        count++;//统计输出顶点数
        for(e=G->adjList[gettop].firstedge;e;e=e->next)
        {//删除以顶点k为尾的弧，并将弧头顶点的入度-1
            int k=e->adjvex;
            if(!(--G->adjList[k].in)//先自减，然后判断减完是否等于0
                stack[++top]=k;//变成入度为0的顶点需要入栈
        }
    }
    if(count<G->numVertexes)
        return ERROR;//存在环，无法得到拓扑序列
    else
        return OK；
}

• 拓扑排序得到的拓扑序列不唯一
• 对于n个顶点和e条边的AOV网，算法时间复杂度为O(n+e)

---

关键路径：解决工程完成需要的最短时间问题

拓扑排序：解决工程能否顺序进行的问题

求解关键路径：解决工程完成需要的最短时间问题

解决工程完成需要最短时间问题前提是工程一定能顺利进行和完成，故拓扑排序是求解关键路径的基础。不存在拓扑序列的有向图无法求解关键路径，求解关键路径之前需进行拓扑排序。

新概念：AOE网

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE（Activity on Edge Network）。正常情况下AOE有一个源点一个汇点

始点/源点：有向图中没有入边的顶点，表示一个工程的开始          终点/汇点：有向图中没有出边的顶点，表示一个工程的结束

如下图所示：

特别强调：

• 某个顶点代表的事件发生后，从该顶点出发的各活动可以立马开始
• 只有在进入某顶点的各活动都已经结束，该顶点代表的事件才能发生

后面的最早最晚时间点根据此处理解，比如事件的最早发生时间，最晚发生时间等等

再介绍几个概念：

路径长度：路径上各个活动所持续时间之和称为路径长度

关键路径：从源点到汇点具有最大长度的路径叫关键路径

关键活动：关键路径上的活动叫关键活动

---

我们的目标：解决工程完成需要的最短时间问题，尽可能缩短工程完成的耗时。

缩短工期长度：只有缩短关键路径上关键活动的时间才能减少整个工期长度

所以，我们需要找到关键路径，缩短关键路径上关键活动的时间，以减少整个工程完成的时间

关键活动:活动的最早开始时间和最晚开始时间相等的话就是意味着此活动是关键活动，活动间的路径为关键路径，否则不是

定义几个参数：

1. etv(earliest time of vertex):顶点事件最早发生的时间点
2. ltv(latest time of vertex):顶点事件最晚发生的时间点，最晚需要开始的时间，超过此时间将会延误工期
3. ete(earliest time of edge):活动最早发生的时间点
4. lte(latest time of edge):活动最晚发生的时间点，不推迟工期的最晚开工时间

我们由1和2来求得3和4，然后根据相对应的活动的ete和lte是否相等判断是否是关键活动

---

先求etv，求etv的过程，就是从头到尾找拓扑序列的过程。

因此在求关键路径之前需调用一次拓扑排序算法计算etv和存储得到的拓扑序列。​​​​​​​

int *etv,*ltv;//事件发生的最早时间和最迟发生时间数组
int *stack2;//存储拓扑序列
int top2;//stack2的栈顶指针

改进过的拓扑排序算法：

不再打印拓扑序列而是存储拓扑序列到Stack2，我们能得到一个拓扑序列，因此能确定工程的源点和终点

Status TopologicalSort(GraphAdjList G)
{
    EdgeNode *e;
    int count=0;//统计输出顶点个数
    int top=0;//栈指针下标
    int *stack;
    stack=(int*)malloc(G->numVertexes*sizeof(int));
    for(int i=0;i<G->numVertexes;i++)
        if(G->adjList[i].in==0)
            stack[++top]=i;//将入度为0的顶点入栈
    etv=(int*)malloc(G->numVertexes*sizeof(int));
    for(int i=0;i<G->numVertexes;i++)
        etv[i]=0;//初始化为0
    int top2=0;//栈顶指针
    stack2=(int*)malloc(G->numVertexes*sizeof(int));
    while(top!=0)
    {
        int gettop=stack[top--];//去stack中入度为0的顶点
        count++;//统计顶点个数，用于最后判断有向图是否有环
        stack2[++top2]=gettop;//将从stack中出来的入度为0的顶点入stack2，stack2中存放拓扑序列
        for(e=G->adjList[gettop].firstedge;e;e=e->next)
        {
            int k=e->adjvex;
            if(!(--G->adjList[k].in)//先自减，然后判断减完是否等于0
                stack[++top]=k;//变成入度为0的顶点需要入栈
            if((etv[gettop]+e->weight)>etv[k])//求各顶点事件最早发生时间
                etv[k]=etv[gettop]+e->weight;
        }
    }
    if(count<G->numVertexes)
        return ERROR;//出错，有环
    else
        return OK;//存在拓扑序列，并存在Stack2中
}         

如何理解：

• 当顶点k为源点时，时间最早开始时间等于0；
• 当顶点k不是源点时，已知该顶点的前驱顶点的最早开始时间，只有进入该顶点的各活动已经结束，该顶点代表的事件才能发生。即该顶点k最早发生时间=max（顶点i事件最早发生的时间点+顶点之间活动的耗时）。举个例子：一个老师最早在下午2点的时候就布置了作业，已知小明大概要做2个小时，小李要做1个半小时，小红要做50分钟，现在问老师最早什么时候能收齐作业。答案不言而喻，需要等小明做完才能收齐作业本吧！应该最早4点才能收齐，3点收作业小明做不完的呀！
• 如下图：

接下来看关键路径算法：

void CriticalPath(GraphAdjList G)
{
    EdgeNode *e;
    int ete,lte;//相应活动的最早发生时间和最迟发生时间变量
    TopologicalSort(G);//先进行拓扑排序
    int ltv=(int*)malloc(G->numVertexes*sizeof(int));//事件最晚发生的时间
    for(int i=0;i<G->numVertexes;i++)//对ltv初始化
        ltv[i]=etv[G->numVertexes-1];//为啥初始化成etv[G->numVertexes-1]？
    //因为根据之前得到拓扑排序得到终点的最早的发生时间，终点事件的最早发生时间等于最晚发生时间
    //为啥呢？既然都到终点了，还分早晚?这个终点的最早发生时间意味着无论如何前面的活动都已经完成
    //此刻已经无需等待,最晚时间没有意义，它之前顶点的最晚时间必须小于终点的最晚发生时间
    while(top2!=0)//拓扑序列的逆序，我们需要从终点倒推出每个事件的最晚发生时间
    {
        int gettop=stack2[top2--];//拓扑序列倒序出栈
        for(e=G->adjList[gettop].firstedge;e;e=e->next)
        {   
            int k=e->adjvex;//k是gettop的领接顶点,有弧<gettop,k>
            if(ltv[k]-e->weight<ltv[gettop])//已知顶点k的最晚发生时间
                ltv[gettop]=ltv[k]-e->weight;//求gettop顶点的最晚发生时间
        }//已知某顶点后序领接顶点事件的最晚发生时间，求该顶点最晚发生时间。见正文分析
    }
    for(int j=0;j<G->numVertexes;j++)
    {   //对每一条弧表示的活动，求活动的最早开始时间，和活动最晚发生时间
        for(e=G->adjList[gettop].firstedge;e;e=e->next)
        {
            int k=e->adjvex;//k是顶点j的后序领接顶点，即存在弧<j,k>表示一个活动
            ete=etv[j];//活动的最早开始时间就等于顶点j表示事件的最早发生时间，
            lte=ltv[k]-e->weight;//活动的最晚发生时间就等于顶点k最晚发生时间减活动所需时间
            if(ete==lte){ //两者相等则此活动没有任何空闲，其在关键路径上，且为关键活动
                printf("<V%d,V%d> length:%d,",//打印输出关键路径
                            G->adjList[j].data,G->adjList[k].data,e->weight);
            }
        }
    }
}

如何理解以上式子：

• 当k=n-1时，表示顶点k是终点。终点的最晚发生时间和最早发生时间是相等的。至于为什么！既然都到终点了，还分早晚?这个终点的最早发生时间意味着无论如何前面的活动都已经完成，此刻已经无需等待,最晚时间没有意义。工程应尽快完成为好。
• 当k！=n-1时，表示顶点k不是终点，且已知顶点j，并且存在活动<k,j>。顶点k最晚发生时间=Min（顶点j最晚发生时间-活动<k,j>活动耗费时间）。举个例子：假设老师打算布置一次作业，老师最晚下午4点要收上去批改作业，现在已知小明大概要做2个小时，小李要做1个半小时，小红要做50分钟，现在好了，为了到时候最晚4点能都收好所以作业，老师应该最晚几点把题目给大家布置出来。当然是最晚2点！如果是3点布置作业会有同学无法完成，所以最晚2点布置，当然1点布置也可以让大家完成。

见下图：

对于活动的最早发生时间ete和最晚发生时间lte：

---

总结：

• 算法的时间复杂度为O(n+e)
• AOE网可能存在多条关键路径，单独提高一条关键路径上的关键活动速度并不能导致整个工程缩短工期，需同时提高几条关键路径上活动的速度。

参考资料：大话数据结构