目录1 .基本概念2 .在AOE网上寻求关键路径的想法3 .代码
1 .基本概念
1.AOV网和AOE网
(1) AOV网)有向图，图中顶点表示活动，边表示活动之间的关系。
例如
在上图中，顶点是课程(活动)，边是课程之间的优先关系。
)2) AOE网)边缘为活动，顶点为事件，边缘上的权重为活动持续的时间的有向图。
例如：
在上图中，边表示事件(购物和搬运货物)，权重表示事件持续的时间，顶点表示事件。
如何理解事件和事件？
边代表活动是需要时间来执行。 例如，买主机是活动，执行起来很花时间。
顶点表示事件，并且瞬间发生，可以表示一些活动的开始，也可以表示一些活动的结束。
我们要研究的关键路径问题就是基于AOE网的。
2. 关键路径
AOE网用来估算工程的完成时间。网中只有一个开始点（入度为零，称为源点），一个结束点 （出度为零，称为汇点）。
AOE网的性质：
（1）只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；
（2）只有在某顶点所代表的事件发生后，从该顶点出发的各活动才开始。
对一项工程来说，整个工程的完成时间为从源点到汇点的权值之和最长的路径，该路径称为关键路径。
用蓝色指示的路径是关键路径。
关键路径上的边(活动)称为关键活动，因为它是如果关键活动的持续时间增加，则完成工程的总时间也要增加，所以称为关键事件。
2 .在AOE网上寻求关键路径的想法是关键路径就是AOE网中从源点到汇点权值之和最大的那条路径。
有如下所示的AOE网络，其中ai表示边缘权重，即活动持续时间。
首先，有以下定义：
符号的含义e(I )活动ai的最早开始时间l ) I )活动ai的最晚开始时间L(I )-e ) I )可以拖多久重新开始活动ai (即完成活动ai的时间充裕) l ) I )=e ) I )是必须立即开始的(ve ) j )顶点j )的最早发生时刻VL(j )顶点j )的最晚发生时刻dut(j )顶点j )和顶点k )之间的边)事件)执行事件注意，在事件)边)
在上图中，有1——6个顶点。
开始
ve(I )的求解方法：首先ve )1)=0)顶点从1开始计数)，依次向后遍历，取ve(k )=max{ve(j ) dut(j，k ) }。
发生
（1）求ve(i):
即通过正向遍历，求出ve(i)
解释：为什么是取最大值？其实很好理解，因为只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；（AOE网性质1）
vl(I )的求法：首先取vl(6)=ve )6)。 也就是说，使最后顶点的ve和vl相等。 这是因为最后一次事件的最早发生时间和最晚发生时间一定相同。 (接着，反方向求出(61 )至VL ) )，有VL ) j )=min{vl(k )
看上图中的顶点4，它有两条路：1-2-4（因为ve(1)=0，所以此时顶点4的发生时间ve(4)为5），另一条路1-3-4（因为ve(1)=0，所以此时顶点4的发生时间ve(4)为6），显然，我们应该让选择更晚的时间作为事件4的最早发生时间（因为如果事件4的最早发生时间早于6，则1-3-4可能还没有全部完成，一个事件发生的最早时间是这一事件之前的所有活动都执行完毕的时间），因此应该取最大值。
（2）求vl(i)：
即通过逆向遍历，求出vl(i)
strong>设ai是弧<j,k>上的活动。（即j，k是顶点，ai是j、k之间的边），dut(<j,k>)表示活动ai的持续时间，则有：
e(i) = ve(i)
l(i) = vl(i) - dut(<j,k>)
解释：活动ai的最早开始时间和事件j的最早发生事件相同，活动ai的最迟开始事件是活动k的最晚开始时间减去活动ai的持续时间，ctddn想想，应该不难理解。
（4）找出e(i) = l(i)的活动（边）
我们在（3）求e(i)和l(i)的过程中，可以找出e(i) = l(i)的活动（边），这些活动就是关键活动，这些活动共同组成了关键路径。
有两点需要注意：
（1）在（1）中求ve(i)时，需要按照拓扑顺序来求，目的是判断该图中是是否有回路，若有回路，则不能求关键路径。（关于拓扑排序看这里）
（2）事件（顶点）的最早开始时间要尽可能的晚（ve(k) = max{ve(j) + dut(<j, k>)}），才能保证该事件前面的活动都发生完了。事件的最晚开始时间要尽可能的早（min{vl(k) - dut(<j, k>)}），才能保证给该事件后面的活动留有充足时间。
3. 代码 #include <iostream>#include <stack>#define MAX_VEX_NUM 20#define OK 1#define ERROR 0typedef char NumType;typedef int Weight;typedef int Status;using namespace std;//以下是用邻接表构建有向图struct ArcNode{ int AdjVex; ArcNode *NextArc; Weight w;};struct VexNode{ NumType Data; int InDegree; ArcNode *FirstArc;};struct ALGraph{ VexNode Vex[MAX_VEX_NUM]; int VexNum; int ArcNum;};int Locate(ALGraph G,NumType v){ int i; for(i=0;i<G.VexNum;i++) if(v==G.Vex[i].Data)return i; return -1;}void CreatALGraph(ALGraph &G){ cout<<"请输入顶点个数："<<endl; cin>>G.VexNum; cout<<"请输入弧的条数："<<endl; cin>>G.ArcNum; cout<<"请输入顶点信息："<<endl; int i,j; for(i=0;i<G.VexNum;i++){cin>>G.Vex[i].Data;G.Vex[i].FirstArc=0;G.Vex[i].InDegree=0;} int k; NumType v1,v2; Weight wei; cout<<"请输入弧的信息："<<endl; for(k=0;k<G.ArcNum;k++) { cin>>v1; cin>>v2; cin>>wei; i=Locate(G,v1);j=Locate(G,v2); G.Vex[j].InDegree++; ArcNode *p=new ArcNode(); *p={j,G.Vex[i].FirstArc,wei}; G.Vex[i].FirstArc=p; }}Status TopoLogicalSort(ALGraph G,stack<int> &T,int *ve){ int i; stack<int> s; for(i=0;i<G.VexNum;i++) if(G.Vex[i].InDegree==0)s.push(i); int j,k; ArcNode *p=0; while(!s.empty()) { j=s.top(); s.pop(); //T用来存拓扑序列 T.push(j); for(p=G.Vex[j].FirstArc;p!=0;p=p->NextArc) { k=p->AdjVex; G.Vex[k].InDegree--; if(!G.Vex[k].InDegree)s.push(k); if(ve[j]+p->w>ve[k])ve[k]=ve[j]+p->w; } }}void CriticalPath(ALGraph G){ int ve[G.VexNum]={0}; stack<int> T; TopoLogicalSort(G,T,ve); int vl[G.VexNum]; int i,j,k; for(i=0;i<G.VexNum;i++)vl[i]=ve[G.VexNum-1];//初始化，很重要 ArcNode *p=0; while(!T.empty()) { //反向拓扑序列输出 j=T.top(); T.pop(); for(p=G.Vex[j].FirstArc;p!=0;p=p->NextArc) { k=p->AdjVex; if(vl[k]-p->w<vl[j])vl[j]=vl[k]-p->w; } } int ee,el; for(j=0;j<G.VexNum;j++) { for(p=G.Vex[j].FirstArc;p!=0;p=p->NextArc) { k=p->AdjVex; ee=ve[j]; el=vl[k]-p->w; if(ee==el)cout<<G.Vex[j].Data<<"-"<<G.Vex[k].Data<<endl; } }}int main(){ ALGraph G; CreatALGraph(G); CriticalPath(G); return 0;}