圖的應(yīng)用：關(guān)鍵路徑

• 思維導(dǎo)圖：
• 關(guān)鍵路徑的定義：
• 步驟：
• 事件最早發(fā)生時間：（權(quán)值最大、出邊）
• 事件最遲發(fā)生時間：（權(quán)值最小、入邊）
• 活動a~i~的最早開始時間:
• 活動a~i~的最遲開始時間:
• 活動a~i~的差額：
• 例：

思維導(dǎo)圖：

關(guān)鍵路徑的定義：

ps：
頂點表示事件，邊表示活動，權(quán)值表示活動的開銷
某一頂點出邊表示的含義： 只有當(dāng)這個事件（頂點）結(jié)束時，才能開始活動（出邊）
以V₁為例，只有當(dāng)V₁事件結(jié)束時，才能同時執(zhí)行a₁和a₂倆個活動
某一頂點入邊表示的含義： 只有當(dāng)所有的活動（所有的入邊）結(jié)束時才能開始事件
以V₄為例，只有當(dāng)a₃和a₅倆個活動結(jié)束后，才能開始V₄事件

步驟：

事件最早發(fā)生時間：（權(quán)值最大、出邊）

ps：

1、以V₁為源點，V₆為匯點
2、計算V₁到V₆的最早發(fā)生時間，就需要計算V₁分別到達V₃、V₄、V₅的最早發(fā)生事件，然后分別加上a₆、a₇、a₈的權(quán)重然后取最大值。
3、以此類推，求V₅的最早發(fā)生時間就需要求V₂的最早發(fā)生時間；求V₄的最早發(fā)生時間就需要求V₂和V₃的 最早發(fā)生時間然后取最大
4、而各個節(jié)點求最早發(fā)生時間的順序是按照拓?fù)渑判虻捻樞騺砬蟮摹?/p>

事件最遲發(fā)生時間：（權(quán)值最小、入邊）

ps：
求最早發(fā)生時間的逆序過程
1、以V₁為源點，V₆為匯點
2、計算V₆到V₁的最遲發(fā)生時間，就需要計算V₃、V₄、V₅的最早發(fā)生事件，然后分別減去a₆、a₇、a₈的權(quán)重然后取最小值。
3、以此類推，求V₅的最遲發(fā)生時間就需要求V₂的最遲發(fā)生時間；求V₄的最遲發(fā)生時間就需要求V₂和V₃的 最遲發(fā)生時間然后取最小
4、而各個節(jié)點求最早發(fā)生時間的順序是按照拓?fù)渑判虻捻樞騺砬蟮摹?/p>

活動a_i的最早開始時間:

ps: 即該邊（活動）弧尾對應(yīng)事件的最早開始時間
以a₈為例，a₈的最早開始時間就是事件V₅的最早開始時間，即e[8] = 6

活動a_i的最遲開始時間:

ps： 即該邊（活動）弧頭對應(yīng)事件 - a_i的權(quán)值
以a₇為例，a₇的最遲開始時間就是V₆的最早開始時間 - a₇，即l[7] = 6

活動a_i的差額：

d(i)為0即說明它為關(guān)鍵路徑，所以這個有向圖的關(guān)鍵路徑為a₂ -> a₅ -> a₇
要對整個工程進行優(yōu)化，就需要對關(guān)鍵路徑進行優(yōu)化

例：

ps： 在強調(diào)一下

V_e(i): 事件的最早發(fā)生時間：從V₁開始，拓?fù)渑判?#xff0c;取最大
V_l(i): 事件的最遲發(fā)生時間：從V₆開始，V₄ = V₆ - a₇，取最小
e(i): 活動的最早發(fā)生時間：弧尾對應(yīng)事件的最早開始時間
l(i): 活動的最遲發(fā)生時間：弧頭對應(yīng)事件最遲開始時間 - a_i的權(quán)值，l(1) = V₂ - a₁ = 9
d(i): 活動的差額：活動的最遲發(fā)生時間 - 活動的最早發(fā)生時間

總結(jié)

以上是生活随笔為你收集整理的数据结构之图的应用：关键路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。