數據結構之關鍵路徑

算法

　　關鍵路徑（Critical Path）從開始點到完成點的路徑長度最長的路徑
 
　　AOE網若在帶權的有向圖中以頂點表示事件以有向邊表示活動邊上的權值表示活動的開銷（如該活動持續的時間）則此帶權的有向圖稱為邊表示活動的網簡稱AOE網
 
　　關鍵活動關鍵路徑上的所有活動

　　求關鍵路徑步驟
　　() 從開始頂點出發計算各事件的最早開始時間令ve()=按拓撲有序求其余各頂點的最早開始時間
　　　ve[k]=max{ve[j]+dut()}　　　　j∈T
　　其中T是以頂點vk為頭的所有弧的尾頂點的集合（≤k≤n）如果得到的拓撲有序序列中的頂點個數小於網中頂點數n則說明該網中存在回路不能求關鍵路徑算法終止否則繼續執行步驟
　　() 從結束頂點vn出發計算各事件的最晚開始時間令vl[n]=ve[n]按拓撲逆序求其余各頂點的最晚開始時間
　　　vl[j]=min{vl[k]dut()}　　　　　k∈S
　　其中S是以頂點vj為尾的所有弧的頭頂點的集合（≤j≤n）
　　() 根據各事件的ve值和vl值求每個活動的最早開始時間e[i]=ve[j]最晚開始時間l[i]=vl(k)dut(＜jk＞)滿足e(i)=l(i)條件的所有活動即為關鍵活動

From:http://tw.wingwit.com/Article/program/sjjg/201311/23787.html