AOE:帶權有向圖-中文百科頻道

AOE 網的定義

AOE網：Activity on edge network AOE 網是在 AOV 網的基礎上，其中每一個邊都具有各自的權值，是一個有向無環網。其中權值表示活動持續的時間。

在一個表示工程的帶權有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權值表示活動的持續時間，稱這樣的有向圖叫做邊表示活動的網，簡稱AOE網。nAOE網中沒有入邊的頂點稱為始點（或源點），沒有出邊的頂點稱為終點（或彙點）。

用法

使用 AOE 網可以幫助解決這樣的問題：如果将 AOE 網看做整個項目，那麼完成整個項目至少需要多少時間？nn解決這個問題的關鍵在于從 AOE 網中找到一條從起始點到結束點長度最長的路徑，這樣就能保證所有的活動在結束之前都能完成。n起始點是入度為 0 的點，稱為“源點”；結束點是出度為 0 的點，稱為“彙點”。這條最長的路徑，被稱為”關鍵路徑“。nn為了求出一個給定 AOE 網的關鍵路徑，需要知道以下 4 個統計數據：n對于 AOE 網中的頂點有兩個時間：最早發生時間（用 Ve(j) 表示）和最晚發生時間（用 Vl(j) 表示）；n對于邊來說，也有兩個時間：最早開始時間（用 e(i) 表示）和最晚開始時間（ l(i) 表示）。nnVe(j)：對于 AOE 網中的任意一個頂點來說，從源點到該點的最長路徑代表着該頂點的最早發生時間，通常用 Ve(j) 表示。n例如，圖 1 中從 V1 到 V5 有兩條路徑，V1 作為源點開始後，a1 和 a2 同時開始活動，但由于 a1 和 a2 活動的時間長度不同，最終 V1-V3-V5 的這條路徑率先完成。但是并不是說 V5 之後的活動就可以開始，而是需要等待 V1-V2-V5 這條路徑也完成之後才能開始。所以對于 V5 來講，Ve(5) = 7。nnVl(j)：表示在不推遲整個工期的前提下，事件 Vk 允許的最晚發生時間。n例如，圖 1 中，在得知整個工期完成的時間是 18 天的前提下，V7 最晚要在第 16 天的時候開始，因為 a10 活動至少需要 2 天時間才能完成，如果在 V7 事件在推遲，就會拖延整個工期。所以，對于 V7 來說，它的 Vl(7)=16。nne(i)：表示活動 ai 的最早開始時間，如果活動 ai 是由弧表示的，那麼活動 ai 的最早開始的時間就等于時間 Vk 的最早發生時間，也就是說：e[i] = ve[k]。ne(i)很好理解，拿圖 1 中 a4 來說，如果 a4 想要開始活動，那麼首先前提就是 V2 事件開始。所以 e[4]=ve[2]。nnl(i)：表示活動 ai 的最晚開始時間，如果活動 ai 是由弧表示，ai 的最晚開始時間的設定要保證 Vj 的最晚發生時間不拖後。所以，l[i]=Vl[j]-len。nn在得知以上四種統計數據後，就可以直接求得 AOE 網中關鍵路徑上的所有的關鍵活動，方法是：對于所有的邊來說，如果它的最早開始時間等于最晚開始時間，稱這條邊所代表的活動為關鍵活動。由關鍵活動構成的路徑為關鍵路徑。