關(guān)鍵路徑
網(wǎng)絡(luò)
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)鍵路徑：具有最大路徑長(zhǎng)度（權(quán)重）的路徑，可能不止一條
活動(dòng)的兩個(gè)屬性：
- e(i)表示最早開(kāi)始時(shí)間
- l(i)表示最晚開(kāi)始時(shí)間
事件的兩個(gè)屬性：
- ve(j)最早開(kāi)始時(shí)間
- vl(j)最晚開(kāi)始時(shí)間
在下面的計(jì)算過(guò)程中，就可以理解這些屬性的概念了
計(jì)算關(guān)鍵路徑的過(guò)程
原理：
- 先求出每個(gè)頂點(diǎn)的ve和vl值
- 通過(guò)這兩個(gè)值就可以求出每條邊的e和l值。
- 取e(i)=l(i)的邊就是
關(guān)鍵路徑上的邊，關(guān)鍵路徑不止一條
一、求ve(i)的值
- 從前向后，直接前驅(qū)節(jié)點(diǎn)的ve值＋當(dāng)前節(jié)點(diǎn)的邊的權(quán)值（有可能多條，取最大值）
- 第一個(gè)頂點(diǎn)的ve等于0
- ve(1) = 0
- ve(2) = ve(1) + len(a1) = 0 + 3 = 3
- ve(3) = ve(1) + len(a3) = 0 + 2 = 2
- ve(4) = ve(1) + len(a2) = 0 + 6 = 6
- ve(5) = min{ve(2) + len(a4),ve(4) + len(a8)} = min{7,7} = 7
- ve(6) = ve(3) + len(a7) = 2 + 3 = 5
- ve(7) = min{ve(a5) + len(a9),ve(6) + len(a10)} = min{10,9} = 10
下表為各頂點(diǎn)（事件）的ve值：
| 頂點(diǎn) | ve(1) | ve(2) | ve(3) | ve(4) | ve（5) | ve(6) | ve(7) |
|---|---|---|---|---|---|---|---|
| ve(i) | 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
- vl(7) = ve(7) = 10
- vl(6) = vl(7) - len(a10) = 10 - 4 = 6
- vl(5) = vl(7) - len(a9) = 10 - 3 = 7
- vl(4) = vl(5) - len(a8) = 7 - 1 = 6
- vl(3) = min{
vl(6) - len(a7),vl(4) - len(a6)} = min{3,5} = 3 - vl(2) = min{
vl(5) - len(a4),vl(4) - len(a5)} = {3,4} = 3 - vl(1) = min{
vl(2) - len(a1),vl(4) - len(a2),vl(3) - len(a3)} = min{0,0,1} = 0
下表為各頂點(diǎn)（事件）的vl值：
| 頂點(diǎn) | vl(1) | vl(2) | vl(3) | vl(4) | vl(5) | vl(6) | vl(7) |
|---|---|---|---|---|---|---|---|
| vl(j) | 0 | 3 | 3 | 6 | 7 | 6 | 10 |
三、求e(i)的值
e(i):活動(dòng)ai是由弧<vk,vj>表示，則活動(dòng)的最早開(kāi)始時(shí)間應(yīng)該和事件vk的最早發(fā)生時(shí)間相等，因此，就有e(i)=ve(k)。即：邊（活動(dòng)）的最早開(kāi)始時(shí)間等于它發(fā)出的頂點(diǎn)(事件)的的最早發(fā)生時(shí)間
參考之前的個(gè)頂點(diǎn)的ve和c：
| 頂點(diǎn) | ve | vl |
|---|---|---|
| v1 | 0 | 0 |
| v2 | 3 | 3 |
| v3 | 2 | 3 |
| v4 | 6 | 6 |
| v5 | 7 | 7 |
| v6 | 5 | 6 |
| v7 | 10 | 10 |
- e(1)、e(2)、e(3) 活動(dòng)（a1、a2、a3三條邊）發(fā)出的頂點(diǎn)為v1，時(shí)間為0
- e(4) 即為
a4這條邊發(fā)出的頂點(diǎn)v2的發(fā)生的時(shí)間ve(2)= 3 - e(5) 即為
a5這條邊發(fā)出的頂點(diǎn)v2的發(fā)生的時(shí)間ve(2)= 3 - e(6) 即為
a6這條邊發(fā)出的頂點(diǎn)v3的發(fā)生的時(shí)間ve(3)= 2 - e(7) 即為
a7這條邊發(fā)出的頂點(diǎn)v3的發(fā)生的時(shí)間ve(3)= 2 - e(8) 即為
a8這條邊發(fā)出的頂點(diǎn)v4的發(fā)生的時(shí)間ve(4)= 6 - e(9) 即為
a9這條邊發(fā)出的頂點(diǎn)v5的發(fā)生的時(shí)間ve(5)= 7 - e(10) 即為
a10這條邊發(fā)出的頂點(diǎn)v6的發(fā)生的時(shí)間ve(6)= 5
得出的e(i)值：
| 邊 | 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)重
參考之前的個(gè)頂點(diǎn)的ve和c：
| 頂點(diǎn) | ve | vl |
|---|---|---|
| v1 | 0 | 0 |
| v2 | 3 | 3 |
| v3 | 2 | 3 |
| v4 | 6 | 6 |
| v5 | 7 | 7 |
| v6 | 5 | 6 |
| v7 | 10 | 10 |
l(i) = 當(dāng)前邊的指向結(jié)點(diǎn)的最晚發(fā)生時(shí)間[vl(i)] - 當(dāng)前時(shí)間（即邊）所消耗的時(shí)間
- l(1) = vl(2) - len(a1) = 3 - 3 = 0
- l(2) = vl(4) - len(a2) = 6 - 6 = 0
- l(3) = vl(3) - len(a3) = 3 - 2 = 1
- l(4) = vl(5) - len(a4) = 7 - 4 = 3
- l(5) = vl(4) - len(a5) = 6 - 2 = 4
- l(6) = vl(4) - len(a6) = 6 - 1 = 5
- l(7) = vl(6) - len(a7) = 6 - 3 = 3
- l(8) = vl(5) - len(a8) = 7 - 1 = 6
- l(9) = vl(7) - len(a9) = 10 - 3 = 7
- l(10) = vl(7) - len(a10) = 10 - 4 = 6
| 邊 | 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)鍵路徑
列出總表：
| 頂點(diǎn) | ve | vl | 活動(dòng) | e | l | l - e | 關(guān)鍵路徑 |
|---|---|---|---|---|---|---|---|
| v1 | 0 | 0 | a1 | 0 | 0 | 0 | √ |
| v2 | 3 | 3 | a2 | 0 | 0 | 0 | √ |
| v3 | 2 | 3 | a3 | 0 | 1 | 1 | |
| v4 | 6 | 6 | a4 | 3 | 3 | 0 | √ |
| v5 | 7 | 7 | a5 | 3 | 4 | 1 | |
| v6 | 5 | 6 | a6 | 2 | 5 | 3 | |
| v7 | 10 | 10 | a7 | 2 | 3 | 1 | |
| a8 | 6 | 6 | 0 | √ | |||
| a9 | 7 | 7 | 0 | √ | |||
| a10 | 5 | 6 | 1 |
其中e(i)==l(i)的邊：
a1 a2 a4 a8 a9
所組成的路徑即為關(guān)鍵路徑：
a1->a4->a9 和 a2->a8->a9
