關鍵路徑
梳理活動的順序僅僅是拓撲排序可以完成的功能之一，更有價值的是估量完成整個事件的最短時間。比如生産一輛汽車，雖然安排員工、準備原始材料是先行條件，但是組裝各種零部件是可以同時進行的，例如制造輪子和發動機、外殼等是可以同時進行的，這樣可以大大減少生産時間。這種場景我們稱為AOE網。
在一個表示工程的帶權有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權值表示活動的持續時間，這種有向圖的邊表示活動的網，稱之為AOE網(Activity On Edge Network)。
我們的目标就是在這樣的AOE網中，确定它的最短完成時間，而具備最短時間的路徑就是關鍵路徑。
把路徑上各個活動所持續的時間之和稱為路徑長度，從起點到終點具有最大長度的路徑叫關鍵路徑，在關鍵路徑上的活動叫關鍵活動。
那麼我們怎麼确定一個活動是不是關鍵活動呢？以做飯為例，我們可以同時燒水、炒菜和熬粥，其中燒水隻需要3分鐘，炒菜需要10分鐘，熬粥需要20分鐘。那麼很顯然至少需要20分鐘才能完成全部工作，也就是說在這20分鐘時間裡，熬粥必須從一開始就進行，而燒水則可以從開始進行，也可以等17分鐘後再進行，炒菜也可以從開始進行，或者最晚等10分鐘後進行。這裡沒有空閑時間的活動就是關鍵活動。
例如下圖就是一個AOE網，其中權值表示活動需要的時間：
以從v0->v3為例，假設權值表示的時間機關為分鐘，可選的路徑有v0->v1->v3，需要8分鐘，或者v0->v2->v3，需要12分鐘。要盡快到達v3，則v2必須一開始立刻啟動，而v1可以在最開始，或者等待4分鐘之後再啟動，是以v0->v2->v3是關鍵路徑。按照此方式，可以得到此AOE網的關鍵路徑如下：
那麼接下來，我們隻需要确認每個頂點的最早開始時間和最晚開始時間，判斷它們的時間差，如果沒有時間差就是關鍵路徑。
代碼實作
首先，我們需要對AOE網進行拓撲排序，在排序的同時還可以得到每個頂點事件的最早發生時間，代碼如下所示：
public boolean topoSort(ATGraph atGraph,int[] earlestTimeVertex,Stack> stack2) { int count = 0; Queue> queue = new LinkedList<>(); for (int i = 0; i < atGraph.getLen(); i++) { if (atGraph.getVertex(i).getIn() == 0) { queue.offer(atGraph.getVertex(i)); } } while (!queue.isEmpty()) { ATVertex vertex = queue.poll(); System.out.print(vertex.getData() + "->"); //将排序的資料push到stack2中 stack2.push(vertex); count++; //擷取第一條邊 ATEdge next = vertex.getNext(); while (next != null) { //擷取 ATVertex nextVertex = next.getVertex(); nextVertex.setIn(nextVertex.getIn() - 1); if (nextVertex.getIn() == 0) { queue.offer(nextVertex); } // 計算每個頂點可以執行的最早時間 // 擷取弧尾頂點下标 int topIndex = atGraph.getVertexIndex(vertex); // 擷取弧頭頂點下标 int index = atGraph.getVertexIndex(nextVertex); // 更新目前頂點可以發生的最早時間 if (earlestTimeVertex[topIndex] + next.getWeight() > earlestTimeVertex[index]) { earlestTimeVertex[index] = earlestTimeVertex[topIndex] + next.getWeight(); } next = next.getNext(); } } return count >= atGraph.getLen();}
現在我們得到了最早發生時間，并且将全部頂點按照通路的先後順序壓進了一個棧中，這是為了友善進行計算最晚發生時間。從前向後計算最晚發生時間是複雜的，但是反過來卻很簡單，對于最後一個頂點，它的最晚發生時間和最早發生時間一定一緻，而它前面的頂點，就必須在此時間點之前完成。參考代碼如下：
for (int i = 0; i < atGraph.getLen(); i++) { // 先将最晚發生時間都設定為最長時間 latestTimeVertex[i] = earlestTimeVertex[atGraph.getLen()-1];}// 從後向前，更新每個頂點的最晚發生時間while (!stack2.isEmpty()){ ATVertex vertex = stack2.pop(); ATEdge next = vertex.getNext(); while (next!=null){ ATVertex nextVertex = next.getVertex(); int nextIndex = atGraph.getVertexIndex(nextVertex); int index = atGraph.getVertexIndex(vertex); if (latestTimeVertex[nextIndex]-next.getWeight()
最後，隻要按照順序比對這兩個時間是否相等，就可以得到完整的關鍵路徑了，完整代碼如下：
public void criticalPath(ATGraph atGraph){ Stack> stack2 = new Stack<>(); int[] earlestTimeVertex = new int[atGraph.getLen()]; int[] latestTimeVertex = new int[atGraph.getLen()]; topoSort(atGraph,earlestTimeVertex,stack2); for (int i = 0; i < atGraph.getLen(); i++) { // 先将最晚發生時間都設定為最長時間 latestTimeVertex[i] = earlestTimeVertex[atGraph.getLen()-1]; } // 從後向前，更新每個頂點的最晚發生時間 while (!stack2.isEmpty()){ ATVertex vertex = stack2.pop(); ATEdge next = vertex.getNext(); while (next!=null){ ATVertex nextVertex = next.getVertex(); int nextIndex = atGraph.getVertexIndex(nextVertex); int index = atGraph.getVertexIndex(vertex); if (latestTimeVertex[nextIndex]-next.getWeight() vertex = atGraph.getVertex(i); ATEdge next = vertex.getNext(); while (next!=null){ ATVertex nextVertex = next.getVertex(); int nextIndex = atGraph.getVertexIndex(nextVertex); lte = latestTimeVertex[nextIndex]-next.getWeight(); ete = earlestTimeVertex[i]; if (ete==lte){ System.out.println("路徑："+atGraph.getVertex(i).getData()+"->"+atGraph.getVertex(nextIndex).getData()+