補充：關(guān)鍵路徑

1、1關(guān)鍵路徑以AOE（activity on edge）網(wǎng)表示。 研究重點：（1）完成整個工程需要多少時間？（2）哪些活動是關(guān)鍵活動，會影響到工程進(jìn)度？如圖：這是一個有向無環(huán)圖。 頂點表示事件，弧表示活動，權(quán)值表示活動的持續(xù)時間。所以，AOE網(wǎng)常用來估算一個工程的完成時間。 右圖：9個事件v1,v2v9，11項活動a1a11。 規(guī)定：整個工程只有一個開始點，一個結(jié)束點。并且入度為0的頂點稱為源點，出度為0稱為匯點。某一事件發(fā)生，說明之前的活動都已完成，之后的活動可以開始。 說明：某些活動可以同時開工。如a1、a2、a3，a7與a8就可以同時開始。2關(guān)鍵路徑完成工程的最短時間是從開始點到完成點的最

2、長路徑長度。指此路徑上的各活動所花費時間之和，不是弧的數(shù)目之和。那么此路徑就稱之為關(guān)鍵路徑。 右圖：v1為開始點，從v1到vj的最長路徑長度稱為vj 的最早發(fā)生時間ve(j)。此時，說明并且以vj為弧頭的工作俱已完成，以vj為弧尾的活動（如ai）可以開始，也稱為ai的最早開始時間，記為e(i)，相對應(yīng)的，不影響工程進(jìn)度的情況下還有一個最遲開工時間，記為l(i)。兩者之差l(i)- e(i)表示活動ai的時間余量。如果某活動的l(i)= e(i)則稱為關(guān)鍵活動。3關(guān)鍵路徑如果有活動ai由弧表示，其持續(xù)時間為dut（），則有：求ve(j)和vl(j)步驟為：1、因為ve(1)=0，從開始點向后遞推

3、：2、因為vl(n)=ve(n)，從完成點向前遞推：4關(guān)鍵路徑所以，求取關(guān)鍵路徑的算法可總結(jié)如下：1、輸入e條弧，建立AOE網(wǎng)；2、從源點（開始點）v1開始，以ve(1)=0為基礎(chǔ)，按照公式求其余各頂點的最早發(fā)生時間ve(j)；注意：若得到的拓?fù)溆行蛐蛄许旤c個數(shù)小于網(wǎng)頂點個數(shù)n，則說明有環(huán)的存在，關(guān)鍵路徑求取失??！3、從匯點（完成點）vn開始，以vl(n)=ve(n)為基礎(chǔ)，按照公式求其余各頂點的最遲發(fā)生時間vl(j)；4、根據(jù)各頂點的ve和vl值，求每條弧（活動）的最早開始時間e(i)和最遲開始時間l(i)，并尋找e(i) = l(i) 的弧，此為關(guān)鍵活動；5、把所有的關(guān)鍵活動及相應(yīng)頂點畫出，即為關(guān)鍵路徑。5關(guān)鍵路徑以右圖為例： 0181814141616066457768710000000000022336664285377777161614141036關(guān)鍵路徑所以關(guān)鍵路徑如右圖所示 問題（2）的回答：在不改變網(wǎng)的關(guān)鍵路徑的前提下 ，提