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

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

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

　　e(i)、l(i)：活動(dòng)i最早、最遲開始時(shí)間。

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

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

　　求頂點(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)的出邊集合。