前面講了AOV網，現在來介紹AOE網。在一個表示工程的有向帶權圖中， 用頂點表示時間，然後用有向邊代表活動，用邊上的權值代表活動持續的時間，這種有向圖的邊表示活動的網，我們稱之為AOE網(Activity on edge network). 我們通常把AOE網站沒有入邊的頂點即入度為零的頂點稱之為源點，而沒有出邊或者出度為0的頂點稱之為終點。正常情況下一個工程會有一個起始事件和終止事件。也就是說隻有一個源點和終點。如下圖所示的是一個AOE網，其中V0為源點，表示一個工程的開始，V9是一個終點，表示整個工程的結束。頂點v0, V1, .......V9分别表示時間，而弧<V0, V1>, <v0, V2>, ..........<V8, V9>都表示一個活動，用a0,a1,......a12表示，他們的值代表者活動持續的時間。
盡管AOE網表示工程流程，所有它具有很明顯的工程的特性。 如果在某個頂點代表的事件發生後， 從該頂點出發的個活動才能開始，隻有進入某頂點的個活動都已經結束後，該頂點所代表的事件才可以發生。AOV網是頂點表示活動的網，他描述的是各個活動之間的制約關系。 而AOE網是邊表示活動的網，表上的權值表示活動的持續時間，是以，AOE網是要建立在活動之間制約關系沒有沖突的基礎之上（滿足AOV網關系基礎），再來分析完成整個工程至少需要的時間，或者說為了縮減完成的工程所需要時間，應當考慮加快哪些活動等一系列問題。
關鍵路徑：我們把AOE網上每條路徑上活動所持續時間之和稱之為路徑長度， 從源點到終點具有最大的長度的路徑叫做關鍵路徑， 在關鍵路徑上的活動叫做關鍵活動。上圖中 開始-發動機完成-部件集中到位-組裝完成 就是一條關鍵路徑，路徑長度為5.5。
對于關鍵路徑對于整個工程的影響會很大，想優化整個工程就必須要考慮從關鍵路徑着手進行優化，比如上圖中代表的整個工期，去改進輪子的産生效率，哪怕是優化成0.1也是沒有多大作用， 隻有縮短關鍵路徑上的關鍵活動，才可以減少整個工期的長度。比如如果發動機的制造時間縮短為2.5， 整個組裝縮短為1.5 ， 那麼關鍵路徑的長度就變成了4.5，整個工程就能早一天完工。
如何求得關鍵路徑，首先要熟悉幾個名詞，事件最早開始時間，事件最晚開始時間，活動最早開始時間， 活動最晚開始時間。有的讀者要開始犯迷糊了，活動開始就開始，哪裡有什麼最早最晚？ 那麼我們舉個例子來說明： boss給你配置設定了個任務，讓你下班以前交工，你一看時間，距離下班還有四個小時時間，但是這個任務你隻需要兩個小時就能做完，假設做完也就能驗收通過。那麼你可以考慮現在立馬開始做任務，做完任務兩個小時的剩餘時間可以看看技術文章什麼的，那你也可以考慮先喝杯下午茶看看文章，兩個小時候在開始做任務，也能在下班前搞定任務。如果把做這個任務當成是一項活動, 那麼現在立馬開始就是0時間開始，也就是最早開始時間， 你也可以選擇兩小時後開始，不能再晚了不然就要加班了。那麼2就是最晚開始時間。 這裡最晚開始時間和最早開始時間不相等，表明你還有空閑時間，這一活動不是關鍵路徑，假如你boss發現了你這個秘密，為了讓你做更多的貢獻，給你加派了兩個小時的工作量，這下可好 最早開始時間和最晚開始時間一緻了，都是0現在立馬開始工作，否則就要加班咯，這樣你就沒有空閑時間了，這一活動就變成了關鍵活動。
關鍵路徑的求得方式就是找到所有活動的最早和最晚開始時間， 如果該活動沒有空餘時間，也就是最早活動時間和最晚活動時間相等， 那麼你該活動就是關鍵活動，關鍵活動組成的一條路徑稱之為關鍵路徑，關鍵路徑可能不唯一，這取決于圖的形态。
與關鍵路徑有關的幾個概念：
⑴事件的最早發生時間ve[k] ：ve[k]是指從始點開始到頂點vk的最大路徑長度。
⑵事件的最遲發生時間vl[k] ：vl[k]是指在不推遲整個工期的前提下,事件vk允許的最晚發生時間。
⑶活動的最早開始時間ete[i] ：若活動ai是由邊<vk→vj>表示，則活動ai的最早開始時間應等于事件vk的最早發生時間。是以有：ete[i]=ve[k]。
⑷活動的最晚開始時間lte[i] ：活動ai的最晚開始時間是指，在不推遲整個工期的前提下，ai必須開始的最晚時間。
若ai由邊<vk→vj>表示，則ai的最晚開始時間要保證事件vj的最遲發生時間不拖後。是以，有：lte[i] = vl[j] - len<vk, vj>; len是ai活動的持續時間。
注意：ete(i) == lte(i) 的活動i叫關鍵活動
關鍵路徑的算法：
可以采取如下步驟求得關鍵活動：
(1)從起點v1出發，令ve（1）=0，按拓撲排序序列求其餘各頂點可能最早發生時間。Ve(k) = max{ ve(j) + len(vj,vk)}
其中j∈T，T是以vk為終點的所有邊的起點集合（2 ≤ k ≤ n）; len(vj, vk)表示vj到vk的邊的長度，即活動權值，下同。
如果得到的拓撲排序序列中頂點的個數小于網絡頂點個數n，則說明網絡中有環，不能求出關鍵路徑，算法結束。
(2)從終點vn出發，令vl(n) = ve(n），按逆拓撲排序序列求其餘各頂點的允許的最遲發生時間：vl(j) = min{ vl(k) - len(vj,vk) }
其中k∈S，S是以起點為vj的所有邊的終點集合（1 ≤ j ≤ n-1）。
(3)求每一項活動ai（1 ≤ i ≤ m）的最早開始時間ete(i) = ve(j）；最晚開始時間：lte(i) = vl(k) - len(vj, vk)，若某條邊滿足 e(i) = l(i) ，則它是關鍵活動。
拓撲排序已經在上一篇文章（拓撲排序）中有過介紹，不在此重複介紹。
code show：
typedef struct edge
{
int AdjVertex;
int weight;
edge* Next;
}EdgeNode;
typedef struct vertex
{
int InDegree;
int Infos;
EdgeNode* FirstEdge;
}VertexNode, AdjList[100];
typedef struct graph
{
AdjList adjlist;
int vernum, edgenum;
}Graph;
int* ve;
int* vl;
stack<int> tstack;
int TopologicalSort(Graph* g)
{
int count = 0;
int idt;
VertexNode node;
EdgeNode* tmp = NULL;
stack<int> stackver; // 輔助棧結構
// 周遊所有頂點，将頂點入度為0的所有頂點都加入棧
for (int i = 0; i < g->vernum; i++)
{
if (g->adjlist[i].InDegree == 0)
{
stackver.push(i);
}
}
ve = (int*) malloc(g->vernum * sizeof(int));
for (int i = 0; i < g->vernum; i++)
{
ve[i] = 0; // 初始化所有事件的最早開始時間
}
// 循環處理所有頂點入度為0的頂點
while(!stackver.empty())
{
idt = stackver.top();
stackver.pop();
count++;
cout << g->adjlist[idt].Infos << endl;
tstack.push(idt); // 将拓撲排序的逆序壓入備用棧
int index;
tmp = g->adjlist[idt].FirstEdge;
while(tmp != NULL) // 周遊頂點為入度為0的頂點，并且處理和其相關的頂點
{
index = tmp->AdjVertex;
g->adjlist[index].InDegree--; // 以該頂點為起點的頂點入度減1
if (g->adjlist[index].InDegree == 0)
{ // 判斷相關連的頂點是否成為新的入度為0的點，滿足條件進行入棧
stackver.push(index);
}
if (ve[idt] + tmp->weight > ve[index]) // 從起點開始計算事件的最早發生時間
ve[index] = ve[idt] + tmp->weight; // 需要滿足所有的拓撲關系
}
}
// 當所有頂點都處理為入度為0，拓撲排序完成
if (count == g->vernum)
{
cout << "Topological sort succeed" << endl;
return 1;
}
// 尚有頂點無法處理說明不是AOV網，是有向帶環圖
cout << "Topological sort failed" << endl;
return 0;
}
void CriticalPath(Graph* g)
{
EdgeNode* e;
int ete, lte; // 活動最早發生的時間和最晚發生的時間
int idt;
if (!TopologicalSort(g))
return;
vl = (int*) malloc(g->vernum * sizeof(int));
for (int i = 0; i < g->vernum; i++)
{
vl[i] = ve[g->vernum-1]; // 初始化所有的最晚發生時間
}
while(!tstack.empty()) // 根據拓撲逆序列來實作最晚時間發生時間的求解，其實就是拓撲排序逆向處理圖
{
idt = tstack.top();
tstack.pop();
e = g->adjlist[idt].FirstEdge;
while(e)
{
int index = e->AdjVertex;
if (vl[index] - e->weight < vl[idt]) // 最早和最晚發生時間 多個事件比對選出全部滿足的最值
vl[idt] = vl[index] - e->weight; // 也就是所有時間的發生都需要完全滿足拓撲關系
e = e->Next;
}
}
// 周遊全部時間來求取關鍵路徑
for (int i = 0; i < g->vernum; i++)
{
e = g->adjlist[i].FirstEdge;
while(e != NULL)
{
int index = e->AdjVertex;
ete = ve[i]; // 活動最早時間
lte = vl[index] - e->weight; // 活動最晚時間
if (ete == lte) // 判斷是否是關鍵活動 即是否空餘時間
{
cout << "<" << g->adjlist[i].Infos << ', ' << g->adjlist[index].Infos << "> ";
}
e = e->Next;
}
}
cout << endl;
}