關(guān)鍵路徑與最短路徑-C

關(guān)鍵路徑

對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問(wèn)題：

1）工程能否順利進(jìn)行對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判?/p>

2）估算整個(gè)工程完成所必須的最短時(shí)間對(duì)AOE網(wǎng)求關(guān)鍵路徑AOE-網(wǎng)AOE－網(wǎng)(ActivityOnEdgeNetwork)：即邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖。其中：頂點(diǎn)表示事件（Event）弧表示活動(dòng)（Activity）權(quán)值表示活動(dòng)持續(xù)的時(shí)間通?？捎肁OE網(wǎng)來(lái)估算工程的完成時(shí)間。上圖AOE-網(wǎng)中：共有11項(xiàng)活動(dòng)：a1,a2,a3,…a11；共有9個(gè)事件：v1,v2,v3,…v9，每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。v9表示整個(gè)工程的結(jié)束v5表示a4和a5已經(jīng)完成，a7和a8可以開(kāi)始與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間v1表示整個(gè)工程的開(kāi)始

由于整個(gè)工程只有一個(gè)開(kāi)始點(diǎn)和一個(gè)完成點(diǎn)，在正常的情況（無(wú)環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)（稱作源點(diǎn)）和一個(gè)出度為零的點(diǎn)（稱作匯點(diǎn)）匯點(diǎn)源點(diǎn)依據(jù)AOE-網(wǎng)可以研究什么問(wèn)題？（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？

完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑。從v1到v9的最長(zhǎng)路徑是（v1,v2,v5,v8,v9），路徑長(zhǎng)度是18。

假設(shè)開(kāi)始點(diǎn)是v1，從v1到vi的最長(zhǎng)路徑長(zhǎng)度叫做事件vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了所有以vi為尾的弧所表示的活動(dòng)的最早開(kāi)始時(shí)間。用e(i)表示活動(dòng)ai的最早開(kāi)始時(shí)間。V9的最早發(fā)生時(shí)間是18事件vi的最早發(fā)生時(shí)間l(i)－e(i)兩者之差意味著完成活動(dòng)ai的時(shí)間余量。我們把l(i)＝e(i)的活動(dòng)叫做關(guān)鍵活動(dòng)。顯然，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)，因此提前完成非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度。a6的最早開(kāi)始時(shí)間是5，最遲開(kāi)始時(shí)間是8。如a6推遲3天開(kāi)始或延遲3天完成，都不會(huì)影響整個(gè)工程的完成。