AOE网对工程管理问题的表示：
 
在有向图中，如果顶点表示事件，有向边表示活动，有向边上的权值表示活动持续时间，这样的有向图称“边表示活动的网”即AOE网。如下图AOE网中，有10个事件，15个活动。
 

 
 
AOE网对比AOV网：
 
（1）AOV网的有向边不考虑权值，而AOE网的有向边考虑权值；
 
（2）AOV网的入度为0的顶点可以有多个，而AOE网入度为0的顶点只有一个；
 
（3）AOV网的出度为0的顶点可以有多个，而AOE网出度为0的顶点只有一个；
 
（4）AOV与AOE网都不允许出现环路。
 
AOE网具有如下性质：
 
（1）只有在进入某一顶点的各条有向边代表的活动结束后，该顶点所代表的事件才能发生；
 
（2）只有在某个顶点代表的事件发生后，从该顶点出发的各条有向边所代表的活动才能开始；
 
（3）在一个AOE网中，有一个入度为0的事件，称源点，它表示整个工程的开始。同时，有一个出度为0的事件，称汇点，它表示整个工程的结束。
 
AOE网的研究目标：
 
（1）完成整个工程需要多少时间？
 
（2）哪些活动是影响工程进度的关键？
 
基本概念：
 
路径长度：AOE网的一条路径上所有活动的总和称为该路径的长度。
 
关键路径：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。
 
关键活动：关键路径上的活动称为关键活动。
 
显然，完成整个工程的最短时间就是AOE网中关键路径的长度。
 
必要说明：为什么最短时间是最大路径长度？
 
拿上图说明，以事件v0为起点，0时开始（以秒为单位）。当时间过去5秒活动a1结束，事件v1发生，而此时，活动a2还差两秒才结束；再过3秒活动a3结束，但此时事件v3还不能发生，因为活动a4刚进行1秒还没有结束，必须再等5秒a4结束，事件v3才能发生。
 
所以，可以得出某一事件的发生，最早也要等前面的所有活动中最消耗时间（即路径最长）的那个活动完成。
 
当一个工程计划用AOE网表示后，所关心的问题就是如何找出关键路径上的关键活动，从而增加关键活动的投入，缩短关键活动持续时间，进而争取整个工程的提前完成。
 
参数定义（假设有n个结点），并对上图AOE网进行计算：
 

 
 
活动持续时间dut(<j，k>)：代表有向边（活动）<j，k>的权值。
 
事件可能的最早开始时间ve(k)：对于顶点vk代表的事件，ve(k)是从源点到该顶点的最大路径长度。递推公式：ve(0)=0；ve(k)=Max{ve(j)+dut(<j,k>)}，由公式，我们从源点v0正向计算。
 
事件允许的最晚发生时间vl(k)：对于顶点vk代表的事件，vl(k)是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间。递推公式：vl(n)=ve(n)；vl(k)=Min{vl(j)-dut(<k,j>)}，由公式，我们从汇点v9反向计算。
 
活动可能的最早开始时间e(i)：对于有向边ai代表的活动，e(i)是该活动的狐尾事件可能的最早发生时间。
 
活动允许的最晚开始时间l(i)：对于有向边ai代表的活动，l(i)是该活动的弧头事件允许的最晚发生时间减去该活动持续的时间。
 
每个活动允许的时间余量就是l(i)-e(i)，而关键活动l(i)-e(i)=0，即可能的最早开始时间等于允许的最晚开始时间。
 
对于上面的AOE网图，把求解的各参数陈述于下表中：
 
 
事件
v0
v1
v2
v3
v4
v5
v6
v7
v8
v9
ve(k)
0
5
7
13
17
18
23
22
26
31
vl(k)
0
10
7
13
17
20
23
22
28
31
 
活动
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
e(i)
0
0
5
7
7
13
13
13
17
17
18
23
23
22
26
l(i)
5
0
10
7
14
13
15
19
17
17
20
26
23
22
28
 由表1，整个工程需要的最少时间为ve(v9)=31。
 
由表2，根据条件l(i)-e(i)=0，得到关键活动有a2，a4，a6，a9，a10，a13，a14；从源点v0到汇点v9的只要经过关键活动的路径就是关键路径，所以该图的关键路径为（v0，v2，v3，v4，v6，v9）和（v0，v2，v3，v4，v7，v9）。
 
寻找关键活动的算法：
 
（1）建立包含n+1个顶点（这样是为了方便n直接代表下标）、e条有向边的AOE网。其中，顶点v0为源点，顶点vn为汇点。
 
（2）根据有向图的拓扑排序算法，求出AOE网的拓扑序列。如果存在环，拓扑序列不存在，则无法得到关键活动，算法失败退出。
 
（3）从源点v0开始，令源点v0的最早开始时间为ve[0]=0，按拓扑序列求其余各顶点k（k=1，2，···，n）的最早开始时间ve[k]。
 
（4）从汇点vn开始，令汇点vn的最晚发生时间vl[n]=ve[n]，按逆拓扑序列求其余各顶点k（k=n-1，n-2，···，0）的最晚发生时间vl[k]。
 
（5）计算每个活动的最早开始时间e[k]。
 
（6）计算每个活动的最晚开始时间l[k]。
 
（7）找出所有e[k]=l[k]的活动k，这些活动即为AOE网的关键活动。
 

 

          从源点到汇点路径长度最长的路径为该工程的关键路径，即关键路径可以保证所有路径的活动都能够完成。
 
      ok，再次进入我们的作业题：
 
      如下图所示的AOE网（弧上权值代表活动的持续天数）
 
           1）完成此工程最少所需要多少天？
            2）哪些是关键活动，在图中表示出关键路径
 
        
 
     我们先计算最早发生时间ve和最迟发生时间vl：
 
 
 
 
1
2
3
4
5
6
7
8
9
10
Ve
0
5
6
12
15
16
16
19
21
23
Vl
0
9
6
12
15
21
16
19
21
23

      首先呢，编号1和编号10分别为该工程的源点和汇点，我们规定最早发生时间ve（源点）=0，最迟发生时间vl（汇点）=ve（汇点）。那么这两个量该如何计算呢，看图：
 

      对于事件i来说，ve(i) = Max{ve(m) + dut(<m, i>)}，vl(i) = Min{vl(j) – dut(<i, j>)}；其中ve(m)代表i前一个事件的最早发生时间，dut(<m, i>)表示从m到i的持续时间，大家可以把它看成一个递归算法，一直调用ve()，直到ve(源点)为止，然后取其最大值，因为它要保证所有路径上的活动都能完成；而最迟发生时间和前者一样，一直递归调用vl()，直到vl(汇点)为止，然后取其最小值即可。
 
    回到原题中对照例图可以很快地得到表格所示内容。
 
    我们再来看两个概念：e(i)和l(i)，前者为活动ai 的最早可能开始时间，后者为活动ai的最迟允许开始时间。区别于前边的ve和vl，e和l为标识的是某活动的时间，而前者是某事件的时间。
 
    假如从事件m到事件i的活动为af，则有e(f)=ve(m), l(f)=vl(i)–dut(<m,i>) ，即活动af的最早可能开始时间为其弧尾事件最早可能发生时间；最迟允许开始时间为其弧尾事件最迟发生时间与两个事件的持续时间之差。是不是感觉有点别扭，但只要理解了这几个关键词也就很容易看懂了。于是乎 e(k) = l(k)的活动就是关键活动 ，请看图表：
 
 
 
 
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
权
5
6
3
6
3
3
4
1
4
5
2
4
2
e
0
0
5
6
6
12
12
15
15
16
19
16
21
l
4
0
9
6
12
12
17
15
15
16
19
21
21

      由图和前边计算的ve和vl可以得到各活动的e和l，如上表所示，则关键活动为a2,a4,a6,a8,a9,a10,a11和a13，所以完成该工程至少需要的天数d=6+6+3+1(4)+5(2)+2=23，该工程的关键路径有两条，即1->3->4->5->7->9->10和1->3->4->5->8->9->10。
 
更新：6号节点的最迟发生时间vl应该是19 而不是21。。。
 
 
 

1，（部分转载）
 
 
 关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序，所以在这里先以拓扑排序开篇。
 
1． 什么是拓扑排序？
 举个例子先：一个软件专业的学生学习一系列的课程，其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边表示先决条件。若课程i是课程j的先决条件，则图中有弧<i,j>。若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列，必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前，若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列，称之为拓扑序列。
 2． 如何实现拓扑排序？
 很简单，两个步骤：
 1． 在有向图中选一个没有前驱的顶点且输出。
 2． 从图中删除该顶点和以它为尾的弧。
 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
 3． 什么是关键路径？
 例子开头仍然，图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2......，v9，每个事件表示在它之前的活动一完成，在它之后的活动可以开始。如v1表示整个工程的开始，v9表示整个工程结束，v5表示a4和a5已完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天。
 
 

 
 
 由于整个工程只有一个开始点和一个完成点，故在正常情况(无环)下，网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
 那么该工程待研究的问题是：1.完成整项工程至少需要多少时间？2.哪些活动是影响工程进度的关键？
 由于在AOE-网中有些活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。
 假设开始点是v1，从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候，也即是l(i)=e(i)的活动，我们称其为关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。
 因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的功效，缩短整个工期。
 
 4． 如何实现关键路径？
 由上面的分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系
 e(i) = ve(j)
 l(i) = vl(k) - dut(<j,k>)
 求解ve(j)和vl(j)需分两个步进行：
 1） 从ve(0)=0开始向前推进求得ve(j)
 Ve(j) = Max{ve(i) + dut(<i,j>) };<i,j>属于T，j=1,2...,n-1
 其中T是所有以第j个顶点为头的弧的集合。
 
 2） 从vl(n-1) = ve(n-1)起向后推进求得vl(j)
 vl(i) = Min{vl(j) - dut(<i,j>};<i,j>属于S，i=n-2,...,0
 其中，S是所有以第i个顶点为尾的弧的集合。
 这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说，ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)必须在Vj的所有后继的最迟发生时间求得之后才能确定。因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
 
 
 具体算法描述如下：
 1． 输入e条弧<j,k>，建立AOE-网的存储结构。
 2． 拓扑排序，并求得ve[]。从源点V0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。
 3． 拓扑逆序，求得vl[]。从汇点Vn出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
 4． 求得关键路径。根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。
 
 为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中，增设一个栈，以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列。
 

 
 
代码（自己编写：）
 
arcnode.h
 
 
#pragma once

class arcnode
{
public:
	arcnode(void);
	arcnode(int x, int y):vertex(x), val(y), nextarc(NULL){}
	~arcnode(void);
public:
	int vertex;
	int val;
	arcnode* nextarc;
};
node.h
#pragma once
#include "arcnode.h"
class node
{
public:
	node(void);
	node(int x):vertex(x), firstarc(NULL){}
	~node(void);
public:
	int vertex;
	arcnode* firstarc;
};
#pragma once
#include "node.h"
class Dgraph
{
public:
	Dgraph(void);
	~Dgraph(void);
	void createGraph(Dgraph &g);
public:
	int vernum;
	int arcnum;
	node* AdjList;
	int *indegree;
	int *outdegree;
};
Dgraph.cpp 
 
 
#include "StdAfx.h"
#include "Dgraph.h"
#include <string>
#include <iostream>
#include <fstream>
using namespace std;


Dgraph::Dgraph(void)
{
}

Dgraph::~Dgraph(void)
{
}
void Dgraph::createGraph(Dgraph &g)
{
	ifstream infile("F:\\test100.txt");
	cout << "读取图的顶点数和边数！" << endl;
	infile >> g.vernum >> g.arcnum;
	cout << g.vernum << ' ' << g.arcnum << endl;
	cout << "开始建立邻接表！" << endl;
	g.indegree = new int[g.vernum];
	g.outdegree = new int[g.vernum];
	g.AdjList = new node[g.vernum];//这里只是调用了node默认的构造函数，所以firstarc还是要重新复制
	for (int i = 0; i < g.vernum; i++)
	{
		g.indegree[i] = 0;
		g.outdegree[i] = 0;
		g.AdjList[i].vertex = i;
		g.AdjList[i].firstarc = NULL;
	}
	int tail, head, val;
	for (int i = 0; i < g.arcnum; i++)
	{
		infile >> tail >> head >> val;
		cout << tail << ' ' << head << ' ' << val << endl;
		arcnode* temp = new arcnode(head, val);
		temp->nextarc = g.AdjList[tail].firstarc;
		g.AdjList[tail].firstarc = temp;
		g.indegree[head]++;
		g.outdegree[tail]++;
	}
}
关键路径.cpp 
 
 
// 关键路径.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "Dgraph.h"
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
struct A 
{
	int tail;
	int head;
};
void topuforearlyfinish(vector<int> &ve, Dgraph g, stack<int> &T)
{
	stack<int> s;
	for (int i = 0; i < g.vernum; i++)
	{
		if (g.indegree[i] == 0)
		{
			s.push(i);
			T.push(i);//入度为0的都入栈
		}
	}
	while (!s.empty())
	{
		int key = s.top();
		s.pop();
		for (arcnode* i = g.AdjList[key].firstarc; i; i = i->nextarc)
		{
			g.indegree[i->vertex]--;
			//下边是求顶点的最早完成时间
			if (ve[key] + i->val > ve[i->vertex])
			{
				ve[i->vertex] = ve[key] + i->val;
			}
			if (g.indegree[i->vertex] == 0)
			{
				s.push(i->vertex);
				T.push(i->vertex);
			}
		}
	}
}
void topuforlastfinish(Dgraph g, stack<int> T, vector<int> ve, vector<int> &vl)
{
	for (unsigned int i = 0; i < vl.size(); i++)
	{
		vl[i] = ve[g.vernum - 1];//最晚完成时间都初始化为最后一个顶点的最早发生时间
	}
	while (!T.empty())
	{
		int key = T.top();
		T.pop();
		for (arcnode* i = g.AdjList[key].firstarc; i; i = i->nextarc)
		{
			//下边就是求顶点的最晚完成时间
			if (vl[i->vertex] - i->val < vl[key])
			{
				vl[key] = vl[i->vertex] - i->val;
			}
		}
	}
}
void CriticalPath(Dgraph g, vector<int> ve, vector<int> vl, vector<A> &path)
{
	for (int i = 0; i < g.vernum; i++)
	{
		for (arcnode* j = g.AdjList[i].firstarc; j; j = j->nextarc)
		{
			if (vl[j->vertex] - j->val == ve[i])
			{
				A temp;
				temp.tail = i;
				temp.head = j->vertex;
				path.push_back(temp);
			}
		}
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	Dgraph g;
	g.createGraph(g);
	vector<int> ve(g.vernum, 0);
	vector<int> vl(g.vernum);
	stack<int> t;
	topuforearlyfinish(ve, g, t);
	topuforlastfinish(g, t, ve, vl);
	vector<A> path;
	CriticalPath(g, ve, vl, path);
	cout << "各项关键活动为：" << endl;
	for (unsigned int i = 0; i < path.size(); i++)
	{
		cout << path[i].tail << "->" << path[i].head << endl;
	}
	system("pause");
	return 0;
}
test100.txt 
 
9 11
 0 1 6
 0 2 4
 0 3 5
 1 4 1
 2 4 1
 3 5 2
 4 6 9
 4 7 7
 5 7 4
 6 8 2
 7 8 4
 
 结果：
 
0->1
 
1->4
 
4->6
 
4->7
 
7->8
 
6->8
 
 
 

  
 
AOE网示例图：
 
 
AOE网：在一个表示工程的带权有向图中，用顶点表示事件（如V0），用有向边表示活动（如<v0,v1> = a1），边上的权值表示活动的持续时间，称这样的有向图为边表示的活动的网，简称AOE网（activity on edge network）
 
源点：
 
在AOE网中，没有入边的顶点称为源点；如顶点V0
 
终点：
 
在AOE网中，没有出边的顶点称为终点；如顶点V3
 
AOE网的性质：
 
【1】只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；
 
         例如：a1和a2活动都结束了，顶点V2所代表的事件才会发生。
 
【2】只有在某顶点所代表的事件发生后，从该顶点出发的各活动才开始；
 
         例如：只有顶点V1所代表的事件结束之后，活动a2和a4才会开始。
 
 
 
在AOE网中，所有活动都完成才能到达终点，因此完成整个工程所必须花费的时间（即最短工期）应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动：
 
 
 
事件的最早发生时间：ve[k]
 
根据AOE网的性质，只有进入Vk的所有活动<Vj, Vk>都结束，Vk代表的事件才能发生，而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以，计算Vk的最早发生时间的方法为：
 
ve[0] = 0
 
ve[k] = max(ve[j] + len<Vj, Vk>)
 
事件的最迟发生时间：vl[k]
 
vl[k]是指在不推迟整个工期的前提下，事件Vk允许的最迟发生时间。根据AOE网的性质，只有顶点Vk代表的事件发生，从Vk出发的活动<Vk, Vj>才能开始，而活动<Vk, Vj>的最晚开始时间为vl[j] - len<Vk, Vj>。
 
活动的最早发生时间：ee[i]
 
ai由有向边<Vk, Vj>，根据AOE网的性质，只有顶点Vk代表的事件发生，活动ai才能开始，即活动ai的最早开始时间等于事件Vk的最早开始时间。
 
活动的最迟发生时间：el[i]
 
el[i]是指在不推迟真个工期的前提下，活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。
 
案例：
 
原始AOE网：
 
 
事件的最早发生时间：ve[k]
 
从源点向终点方向计算
 
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
 
事件的最迟发生时间：vl[k]
 
从终点向源点方向计算
 
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 
 
活动的最早发生时间：ee[i]
 
共有五个活动：
 
ee[0] = ve[0] = 0
 
ee[1] = ve[0] = 0
 
ee[2] = ve[1] = 4
 
ee[3] = ve[2] = 6
 
ee[4] = ve[1] = 4
 
活动的最迟发生时间：el[i]
 
el[0] = v[1] - a0 = 4 - 4 = 0
 
el[1] = vl[2] - a1 = 6 - 3 = 3
 
el[2] = vl[2] - a2 = 6 - 2 = 4
 
el[3] = vl[3] - a3 = 10 - 4 = 6
 
el[4] = vl[3] - a4 = 10 - 6 = 4
 
 
 
活动的最早开始时间和最晚开始时间相等，则说明该活动时属于关键路径上的活动，即关键活动。
 
经过比较，得出关键活动有：a0, a2, a3, a4，画出示意图如下：
 
 
该AOE网有两条关键路径。
 
所以，通过此案例也可以发现，一个AOE网的关键路径可能有多条。