數(shù)據(jù)結(jié)構(gòu)圖關(guān)鍵路徑
AOV網(wǎng)絡(luò)：有向圖，用頂點(diǎn)表示活動(dòng)寞酿，用弧表示活動(dòng)的先后順序
AOE網(wǎng)絡(luò)：有向圖，用頂點(diǎn)表示事件，用弧表示活動(dòng)，用權(quán)值表示活動(dòng)消耗時(shí)間
名詞解釋
活動(dòng)：業(yè)務(wù)邏輯中的行為队他，用邊表示
事件：活動(dòng)的結(jié)果或者觸發(fā)條件
關(guān)鍵路徑：具有最大路徑長度（權(quán)重）的路徑牺汤，可能不止一條
活動(dòng)的兩個(gè)屬性：e(i)最早開始時(shí)間，l(i)最晚開始時(shí)間
事件的兩個(gè)屬性：ve(j)最早開始時(shí)間珠增，vl(j)最晚開始時(shí)間
在下面的計(jì)算過程中，就可以理解這些屬性的概念了
計(jì)算關(guān)鍵路徑的過程
原理：
- 先求出每個(gè)頂點(diǎn)的ve和vl值
- 通過這兩個(gè)值就可以求出每條邊的e和l值砍艾。
- 取e(i)=l(i)的邊就是
關(guān)鍵路徑上的邊蒂教，關(guān)鍵路徑不止一條
一、求ve(j)的值
- 從前向后脆荷，直接前驅(qū)節(jié)點(diǎn)的ve值＋當(dāng)前節(jié)點(diǎn)的邊的權(quán)值（有可能多條凝垛，取最大值）
- 第一個(gè)頂點(diǎn)的ve等于0
下表為各頂點(diǎn)（事件）的ve值：
| 頂點(diǎn) | v1 | v2 | v3 | v4 | v5 | v6 | v7 |
|---|---|---|---|---|---|---|---|
| ve(j) | 0 | 3 | 2 | 6 | 7 | 5 | 10 |
二、求vl(j)的值
- 從后向前蜓谋，直接后繼節(jié)點(diǎn)的vl值－當(dāng)前節(jié)點(diǎn)的邊的權(quán)值（有可能多條梦皮，取最小值）
- 終結(jié)點(diǎn)的vl等于它的ve
| 頂點(diǎn) | v1 | v2 | v3 | v4 | v5 | v6 | v7 |
|---|---|---|---|---|---|---|---|
| vl(j) | 0 | 3 | 3 | 6 | 7 | 6 | 10 |
三、求e(i)的值
e(i):活動(dòng)ai是由弧<vk,vj>表示桃焕，則活動(dòng)的最早開始時(shí)間應(yīng)該和事件vk的最早發(fā)生時(shí)間相等剑肯，因此，就有e(i)=ve(k)观堂。即：邊（活動(dòng)）的最早開始時(shí)間等于它發(fā)出的頂點(diǎn)(事件)的的最早發(fā)生時(shí)間
| 邊 | a1(3) | a2(6) | a3(2) | a4(4) | a5(2) | a6(1) | a7(3) | a8(1) | a9(3) | a10(4) |
|---|---|---|---|---|---|---|---|---|---|---|
| e(i) | 0 | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 7 | 5 |
四让网、求l(i)的值
l(i):活動(dòng)ai是由弧<vk,vj>表示，則ai的最晚發(fā)生時(shí)間要保證vj的最遲發(fā)生時(shí)間不拖后（vj最遲發(fā)生時(shí)間為9的話师痕，ai的最遲時(shí)間就必須是 9-活動(dòng)耗時(shí) ）溃睹。因此，l(i)=vl(i)-len<vk,vj>七兜，即：活動(dòng)到達(dá)頂點(diǎn)的最晚發(fā)生時(shí)間減去邊的權(quán)重
| 邊 | a1(3) | a2(6) | a3(2) | a4(4) | a5(2) | a6(1) | a7(3) | a8(1) | a9(3) | a10(4) |
|---|---|---|---|---|---|---|---|---|---|---|
| l(i) | 0 | 0 | 1 | 3 | 4 | 5 | 3 | 6 | 7 | 6 |
五丸凭、求出關(guān)鍵邊和關(guān)鍵路徑
e(i)==l(i)的邊：
a1 a2 a4 a8 a9
關(guān)鍵路徑：
a1->a4->a9 和 a2->a8->a9
