概念
AOE網(wǎng)對應(yīng)研究實際問題是工程的工期問題：（1）完成一項工程至少需要多少時間耀态？（2）哪些活動是影響整個工程進度的關(guān)鍵瘩燥？
如果在有向圖中用頂點表示事件，用弧表示活動正林，用弧上的權(quán)表示活動持續(xù)時間，則稱該帶權(quán)有向圖(即有向網(wǎng))為邊表示活動的網(wǎng)(activity on edge network)颤殴，簡稱AOE網(wǎng)觅廓。如下圖所示：
AOE網(wǎng)中的事件與活動有如下兩個重要性質(zhì)：
1、只有在某頂點所代表的事件發(fā)生后涵但，從該頂點出發(fā)的各活動才能開始杈绸；
2、只有在進入某頂點的各活動都結(jié)束矮瘟，該頂點所代表的事件才能發(fā)生瞳脓。
由于一個工程只可能有一個開始點和一個完成點，故正常情況（無環(huán)）下澈侠，網(wǎng)中只可能有一個入度為0的節(jié)點（稱為源點）和一個出度為0的節(jié)點（稱為匯點）劫侧。
通常在一個工程中一些活動可以并行地進行，另一些活動則需要等待前面所有的活動完成后才能開始（因此哨啃，這里還涉及到事件的拓撲排序）烧栋，所以完成整個工程的最短時間應(yīng)該是從開始點到結(jié)束點的最長路徑的長度（指的是活動持續(xù)時間之和，而非弧的數(shù)目）拳球。路徑長度最長的那條路徑叫做關(guān)鍵路徑审姓，關(guān)鍵路徑上的活動稱為關(guān)鍵活動。因此祝峻，提前完成非關(guān)鍵活動并不能加快工程的進度魔吐。
與關(guān)鍵活動有關(guān)的量
如果我們用e(i)標識活動a(i)的最早開始時間，l(i)表示活動a(i)的最遲開始時間（這是在不推遲整個工程完成的前提下活動a(i)的最遲必須開始的時間）莱找，兩者之差l(i) - e(i)意味著活動a(i)的時間余量酬姆。僅當(dāng)活動a(i)滿足條件l(i) == e(i)（即活動的時間余量為0）時表示為關(guān)鍵活動。
因此宋距，要獲得工程的關(guān)鍵路徑就是找出滿足條件l(i) == e(i)的所有活動（一個工程中可能存在多條關(guān)鍵路徑）轴踱。
為了求得活動的e(i)和l(i)，首先應(yīng)求得事件的最早發(fā)生時間ve(j)谚赎，和最遲發(fā)生時間vl(j)淫僻。如果活動a(i)由弧<j, k>表示诱篷，其持續(xù)時間記為dut(<j, k>)，則滿足如下關(guān)系式：
e(i) = ve(j)
l(i) = vl(k) - dut(<j, k>)
事件的最早發(fā)生時間ve(j)：是指從始點開始到頂點（事件）j的最大路徑長度雳灵。這個長度決定了所有從頂點j出發(fā)的活動能夠開工的最早時間棕所。
從開始點往后遞推求取：
ve(0) = 0; ve(j) = Max{ve(i) + dut(<i, j>) }, 其中<i, j>∈T, j = 1, 2, ..., n -1; T為節(jié)點j的入度邊集合悯辙。
事件最遲發(fā)生時間vl(j)：是指在不推遲整個工期的前提下,事件j允許的最晚發(fā)生時間琳省。
從結(jié)束點往前遞推求取：
vl(n - 1) = ve(n - 1); vl(i) = Min{vl(j) - dut(<i, j>)},其中<i, j>∈S, i = n - 2, ..., 0; S為節(jié)點i的出度邊集合躲撰。
示例
利用Guava的graph數(shù)據(jù)結(jié)構(gòu)求得如下所示工程圖的關(guān)鍵路徑针贬。graph的使用相關(guān)介紹請參考：圖論（2）：Guava中Graph模塊(wiki翻譯)
1、構(gòu)建示例圖AOE網(wǎng)的數(shù)據(jù)結(jié)構(gòu)：
MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed()
.nodeOrder(ElementOrder.insertion())
.expectedNodeCount(10)
.build();
graph.putEdgeValue(V1, V2, 6);
graph.putEdgeValue(V1, V3, 4);
graph.putEdgeValue(V1, V4, 5);
graph.putEdgeValue(V2, V5, 1);
graph.putEdgeValue(V3, V5, 1);
graph.putEdgeValue(V4, V6, 2);
graph.putEdgeValue(V5, V7, 9);
graph.putEdgeValue(V5, V8, 7);
graph.putEdgeValue(V6, V8, 4);
graph.putEdgeValue(V7, V9, 2);
graph.putEdgeValue(V8, V9, 4);
Log.i(TAG, "graph: " + graph);
輸出：
nodes: [v1, v2, v3, v4, v5, v6, v7, v8, v9],
edges: {<v1 -> v4>=5, <v1 -> v2>=6, <v1 -> v3>=4,
<v2 -> v5>=1, <v3 -> v5>=1, <v4 -> v6>=2, <v5 -> v8>=7,
<v5 -> v7>=9, <v6 -> v8>=4, <v7 -> v9>=2, <v8 -> v9>=4}
2拢蛋、獲取該有向圖的拓撲排序列表：
/**
* 利用Traverser接口將graph進行拓撲排序topologically桦他，此處返回的逆拓撲排序
*/
Iterable<String> topologicallys = Traverser.forGraph(graph)
.depthFirstPostOrder(startNode);
Log.i(TAG, "topologically: " + format(topologicallys));
輸出：
topologically: {v9,v8,v6,v4,v7,v5,v2,v3,v1} //這里是逆序
3、遞推求得ve(j)值：
//獲取ve(i)
Map<String, Integer> ves = getVeValues(graph, topologicallys);
Log.i(TAG, "ves: " + format(ves));
/**
* ve(j) = Max{ve(i) + dut(<i,j>) }; <i,j>屬于T谆棱，j=1,2...,n-1
* @param graph
* @param topologicallys
* @return
*/
private static Map<String, Integer> getVeValues(ValueGraph<String, Integer> graph,
Iterable<String> topologicallys) {
List<String> reverses = Lists.newArrayList(topologicallys.iterator());
Collections.reverse(reverses); //將逆拓撲排序反向
Map<String, Integer> ves = new ArrayMap<>(); //結(jié)果集
//從前往后遍歷
for (String node : reverses) {
ves.put(node, 0); //每個節(jié)點的ve值初始為0
//獲取node的前趨列表
Set<String> predecessors = graph.predecessors(node);
int maxValue = 0;
//找前趨節(jié)點+當(dāng)前活動耗時最大的值為當(dāng)前節(jié)點的ve值
for (String predecessor : predecessors) {
maxValue = Math.max(ves.get(predecessor) +
graph.edgeValueOrDefault(predecessor, node, 0), maxValue);
}
ves.put(node, maxValue);
}
return ves;
}
輸出：
ves: {v1:0, v2:6, v3:4, v4:5, v5:7, v6:7, v7:16, v8:14, v9:18}
4快压、遞推求得vl(j)值：
/**
* vl(i) = Min{vl(j) - dut(<i,j>}; <i,j>屬于S，i=n-2,...,0
* @param graph
* @param topologicallys
* @param vels
* @return
*/
private static Map<String, Integer> getVlValues(ValueGraph<String, Integer> graph,
Iterable<String> topologicallys, Map<String, Integer> vels) {
Map<String, Integer> vls = new ArrayMap<>(); //結(jié)果集
//從后往前遍歷
for (String node : topologicallys) {
//獲取node的后繼列表
Set<String> successors = graph.successors(node);
int initValue = Integer.MAX_VALUE; //初始值為最大值
if (successors.size() <= 0) { //表示是結(jié)束點垃瞧，賦值為ve值
initValue = vels.get(node);
}
vls.put(node, initValue);
int minValue = initValue;
//找后繼節(jié)點-當(dāng)前活動耗時最少的值為當(dāng)前節(jié)點的vl值
for (String successor : successors) {
minValue = Math.min(vls.get(successor) -
graph.edgeValueOrDefault(node, successor, 0), minValue);
}
vls.put(node, minValue);
}
return vls;
}
輸出：
vls: {v1:0, v2:6, v3:6, v4:8, v5:7, v6:10, v7:16, v8:14, v9:18}
5蔫劣、根據(jù)前面求取的ve(j)和vl(j)來找出關(guān)鍵活動（判斷條件：ve(j) == vl(k) - dut(<j,k>)）：
/**
* 判斷條件：ve(j) == vl(k) - dut(<j,k>)
*/
//關(guān)鍵活動結(jié)果集
List<EndpointPair<String>> criticalActives = new ArrayList<>();
//返回圖中所有活動(邊)
Set<EndpointPair<String>> edgs = graph.edges();
//遍歷每一條邊（活動），過濾出：ve(j) == vl(k) - dut<j, k>
for (EndpointPair<String> endpoint : edgs) {
final int dut = graph.edgeValueOrDefault(endpoint.nodeU(), endpoint.nodeV(), 0);
//ve(j) == vl(k) - dut<j, k>
if (vls.get(endpoint.nodeV()) - dut == ves.get(endpoint.nodeU())) {
criticalActives.add(endpoint);
}
}
Log.i(TAG, "critical actives: " + format(criticalActives));
輸出：
critical actives: {<v1 -> v2>, <v2 -> v5>, <v5 -> v8>, <v5 -> v7>,
<v7 -> v9>, <v8 -> v9>}
從輸出可知个从，圖中存在兩條關(guān)鍵路徑：{<v1 -> v2>, <v2 -> v5>, <v5 -> v8>, <v8 -> v9>} 和 {<v1 -> v2>, <v2 -> v5>, <v5 -> v7>, <v8 -> v9>}(在示例圖中使用紅色線段標注)脉幢。因此，縮短這兩條路徑上活動的工期信姓，將能有效的縮短整個工程的工期鸵隧。
關(guān)鍵路徑詳細代碼參見Demo：GH-Demo-CriticalPath。
