2010軟件水平考試軟件設(shè)計師重點(diǎn)難點(diǎn)輔導(dǎo)(3)

　　為了找出給定的AOE網(wǎng)絡(luò)的關(guān)鍵活動，從而找出關(guān)鍵路徑，先定義幾個重要的量：

　　Ve(j)、Vl(j) ：頂點(diǎn)j事件最早、最遲發(fā)生時間。

　　e(i)、l(i)：活動i最早、最遲開始時間。

　　從源點(diǎn)V1到某頂點(diǎn)Vj的最長路徑長度稱為事件Vj的最早發(fā)生時間，記為Ve(j)。Ve(j)也是以Vj為起點(diǎn)的出邊所表示的活動ai的最早開始時間e(i)。

　　在不推遲整個工程完成的前提下，一個事件Vj允許的最遲發(fā)生時間記為Vl(j)。顯然，l(i) =Vl( j)-(ai所需時間)，其中j為ai活動的終點(diǎn)。滿足條件l(i) =e(i)的活動為關(guān)鍵活動。

　　求頂點(diǎn)Vj的Ve(j)和Vl(j)可按以下兩步來做。

　　(1)由源點(diǎn)開始向匯點(diǎn)遞推。

　　其中，E1是網(wǎng)絡(luò)中以Vj為終點(diǎn)的入邊集合。

　　(2)由匯點(diǎn)開始向源點(diǎn)遞推。

　　其中，E2是網(wǎng)絡(luò)中以Vj為起點(diǎn)的出邊集合。