AOV網絡和AOE網絡

AOV和AOE網絡是什麼

活動網絡可以用來描述生産計劃、施工過程、生産流程、程式流程等工程中各子工程的安排問題。活動網絡可分為兩種：AOV網絡和AOE網絡

AOV網絡（Activity On Vertices）：在有向圖中，用頂點表示活動，用有向邊u->v來表示活動u必須先于活動v進行

AOE網絡（Activity on edge network）：若在帶權的有向圖中，以頂點表示階段，以有向邊u->v表示活動活動u必須先于活動v進行，邊上的權值表示活動的開銷（如該活動持續的時間）

 針對AOV網絡的拓撲排序算法

為AOV網絡進行管理：決定每個結點的先後順序（不一定是唯一的），也就決定了活動的先後順序

拓撲排序（Topological Sort）見：算法導論第22章：基本的圖算法

針對AOE網絡的關鍵路徑算法 

關鍵路徑（Critical Path）：從源點到彙點具有最大長度的路徑。這條路徑決定了整個項目的最早完成時間，要想優化整個項目的時間，則必須在關鍵路徑上下手。

最早完成時間：項目到達某個階段至少需要的時間，即源點到相應頂點的最長路徑。

最遲完成時間：項目最遲完成的時間，超過此時間表示項目産生了停滞。

**算法思想：拓撲序DP**

算法描述：

從源點開始，更新其所有鄰接結點的最早完成時間，直到彙點（項目的終止點）

按拓撲逆序DP，獲得所有結點的最遲完成時間

若最早完成時間 == 最遲完成時間，則證明其為關鍵路徑上的結點

參考資料

算法學習記錄-圖——應用之關鍵路徑（Critical Path）

AOV網絡與拓撲（一）