模塊三非線性結(jié)構(gòu)--圖關(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)什么是AOE網(wǎng)關(guān)鍵路徑邊表示活動的網(wǎng)(ActivityOnEdgeNetwork，簡稱為AOE網(wǎng))，為帶權(quán)有向無環(huán)圖。其中：頂點(diǎn)表示事件，邊表示活動，邊的權(quán)值表示活動持續(xù)的時間。一、基本概念v1v2v3v4v53813223一個AOE網(wǎng)a1a2a3a4a5a6a7其中：AOE網(wǎng)中頂點(diǎn)表示的事件實(shí)際上體現(xiàn)了一種狀態(tài)，即該頂點(diǎn)的所有入邊表示的活動均已完成，出邊表示的活動可以開始。關(guān)鍵路徑二、關(guān)鍵路徑的問題源點(diǎn):表示整個工程的開始點(diǎn)，也稱為起點(diǎn)，是那一些在網(wǎng)上面入度為零的結(jié)點(diǎn)。匯點(diǎn):表示整個工程的結(jié)束點(diǎn)，也稱之為收點(diǎn)，是一些出度為零的頂點(diǎn)。一張AOE的網(wǎng)，它僅僅只有一個源點(diǎn)以及一個匯點(diǎn)。1、邊表示活動的網(wǎng)(ActivityOnEdgeNetwork，簡稱為AOE網(wǎng))為帶權(quán)有向無環(huán)圖，其中：頂點(diǎn)表示事件，邊表示活動，邊的權(quán)值表示活動持續(xù)的時間。其中：AOE網(wǎng)中頂點(diǎn)表示的事件實(shí)際上體現(xiàn)了一種狀態(tài)，即該頂點(diǎn)的所有入邊表示的活動均已完成，出邊表示的活動可以開始。v1v2v3v4v53813223一個AOE網(wǎng)a1a2a3a4a5a6a7一、基本概念v1v2v3v4v53813223a1a2a3a4a5a6a73、關(guān)鍵路徑：由于AOE網(wǎng)中的若干活動是可以并行進(jìn)行的，所以完成工程的最短時間是從源點(diǎn)到匯點(diǎn)的最長路徑的長度，即最長路徑上各邊權(quán)值之和。從源點(diǎn)到匯點(diǎn)的最長路徑稱為關(guān)鍵路徑。AOE網(wǎng)中的關(guān)鍵路徑可能不止一條。

事件vj可能的最早發(fā)生時間ve(j)

應(yīng)為從源點(diǎn)到頂點(diǎn)vj的最長路徑長度弧<vj,vk>表示的活動ai的最早開始時間e(i)等于ve(j)。在不推遲整個工程完成的前提下，事件vk允許的最遲發(fā)生時間vl(k)應(yīng)等于匯點(diǎn)vn的最早發(fā)生時間ve(n)減去vk到vn的最長路徑長度。

弧<vj,vk>表示的活動ai的最遲開始時間l(i)等于vl(k)減去弧<vj,vk>的權(quán)值。4、若活動ai是弧<j,k>，持續(xù)時間是dut(<j,k>)，設(shè)：ve(j)、e(i)、vl(k)、l(i)5、關(guān)鍵活動：對活動ai而言，l(i)-e(i)為其在不延誤整個工程工期情況下，可以延遲的時間。若e(i)=l(i)則稱活