【AOE 網】

在表示一個工程時，用頂點表示事件，用弧表示活動，權值表示活動的持續時間，這樣的有向圖即為 AOE 網。

其有兩個性質：

• 在頂點表示事件發生之后，從該頂點出發的有向弧所表示的活動才能開始。
• 在進入某個頂點的有向弧所表示的活動完成之后，該頂點表示的事件才能發生。

對于一個工程來說，只有一個開始狀態和一個結束狀態，因此在 AOE 網中，只有一個入度為 0 的點表示工程的開始，即源點，也只有一個出度為 0 的點表示工程的結束，即匯點。

AOE 網常用于進行工程管理，其解決的主要問題是：

• 計算完成整個工程的最短工期
• 確定關鍵路徑，以找出哪些活動是影響工程進度的關鍵

【關鍵路徑】

在 AOE 網上，從源點到匯點的具最大路徑長度（該路徑上行各活動持續時間的和）的路徑稱為關鍵路徑，關鍵路徑上的活動稱為關鍵活動。

要找出關鍵路徑，就要找出關鍵活動，即不按期完成就會影響整個工程的活動。

1.事件 vk?的最早發生時間?ve[k]

在保證整個工程完成的前提下，事件最早的開始時間稱為事件 vk?的最早發生時間，記作：ve[k]

ve[k] 的大小實際上為從源點開始到頂點 vk?的最大路徑長度，那么，求解 ve[k] 可以從源點 ve[1]=0 開始，按照拓撲排序規則遞推得到

即有：

其中，len<vj,vk>?是弧 <vj,vk>?上的權值，p[k] 是所有到達 vk?的有向邊的集合。

2.事件 vk?的最晚發生時間 vl[k]

在保證整個工程完成的前提下，事件最遲的開始時間稱為事件 vk?的最晚發生時間，記作 vl[k]

求解 vl[k] 可以從匯點 vl[n]=ve[n] 開始，向源點遞推得到，即有：

其中，len<vk,vj>?是弧 <vk,vj>?上的權值，s[k] 是所有從?vk?發出的有向邊的集合。

3.活動 ai 的最早開始時間 ee[i]

在保證工程順利完成的基礎上，活動 ai 最早的必須開始時間稱為活動 ai 的最早開始時間，記作：ee[i]

若活動 ai 是由弧 <vk,vj> 表示，根據 AOE 網的性質，只有事件 vk 發生后，活動 ai 才能開始

那么也就是說，活動 ai 的最早開始時間等于時間 vk 的最早發生時間，即有：

4.活動 ai 的最晚開始時間 el[i]

在不推遲整個工程完成時間的基礎上，活動 ai 最遲的必須開始時間稱為活動 ai 的最晚開始時間，記作：el[i]

若活動 ai 是由弧 <vk,vj> 表示，則 ai 的最晚開始時間要保證時間 vj 的最遲發生時間不拖后，即有：

其中，len<vk,vj>?是弧 <vk,vj>?上的權值

5.活動 ai 的松弛時間 el[i]-ee[i]

活動 ai 的最晚開始時間與最早開始時間的差值稱為活動 ai 的松弛時間，記作：el[i]-ee[i]

當 el[i]=ee[i] 時，對應的活動 ai 稱為關鍵活動，那些 el[i]>ee[i] 的活動則不是關鍵活動。

在關鍵活動確定后，關鍵活動所在的路徑就是關鍵路徑。

【實現】

1.輸出關鍵路徑

根據關鍵路徑的定義，依次求出?ve、vl、ee、el，然后比較 ee、el 進行輸出

int n,m; int G[N][N];//鄰接矩陣 int in[N];//入度 int ve[N];//事件vk的最早發生時間 int vl[N];//事件vk的最晚發生時間 int ee[N];//活動ai的最早開始時間 int el[N];//活動ai的最晚開始時間 int Stack[N];//棧 struct Edge {int x,y;int dis;Edge(){}Edge(int x,int y,int dis):x(x),y(y),dis(dis){} }edge[N]; bool vis[N];void getVe(){//求veint cnt=0;for(int i=1;i<=n;i++){int k=-1;for(int j=1;j<=n;j++){if(in[j]==0){Stack[++cnt]=j;k=j;in[j]=-1;break;}}for(int j=1;j<=n;j++){if(G[k][j]!=INF){ve[j]=max(ve[j],ve[k]+G[k][j]);in[j]--;}}} } void getVl(){//求vlmemset(vl,INF,sizeof(vl));vl[Stack[n]]=ve[Stack[n]];for(int i=n;i>=1;i--){for(int j=1;j<=n;j++){if(G[Stack[i]][j]!=INF) {vl[Stack[i]]=min(vl[j]-G[Stack[i]][j],vl[Stack[i]]);}}} } void getEe(){//求eefor(int i=1;i<=m;i++)ee[i]=ve[edge[i].x]; } void getEl(){//求elfor(int i=1;i<=m;i++)el[i]=vl[edge[i].y]-edge[i].dis; }void printEdge(){//以邊輸出for(int i=1;i<=m;i++)if(ee[i]==el[i])printf("<%d,%d>:%d\n", edge[i].x, edge[i].y, edge[i].dis); } void printNode(){//以點輸出priority_queue<int,vector<int>,greater<int> > Q;memset(vis,false,sizeof(vis));for(int i=1;i<=m;i++){if(ee[i]==el[i]){int x=edge[i].x;int y=edge[i].y;if(!vis[x]){Q.push(x);vis[x]=true;}if(!vis[y]){Q.push(y);vis[y]=true;}}}while(!Q.empty()){int temp=Q.top();Q.pop();printf("v%d ",temp);} } int main() {memset(G,INF,sizeof(G));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,dis;scanf("%d%d%d",&x,&y,&dis);edge[i].x=x;edge[i].y=y;edge[i].dis=dis;G[x][y]=dis;in[y]++;}getVe();getVl();getEe();getEl();printf("以邊輸出：\n");printEdge();printf("以點輸出：\n");printNode();return 0; }

2.求關鍵路徑長度

由于關鍵路徑是具有最大路徑長度的路徑，因此直接求有向圖的最長路即為關鍵路徑的長度

struct Node{int to,dis;Node(){}Node(int to,int dis):to(to),dis(dis){} }; int n,m; int in[N]; vector<Node>G[N]; int dis[N]; void getPath() {queue<int> Q;for(int i=0;i<n;i++){if(in[i]==0){Q.push(i);dis[i]++;}}while(!Q.empty()){int x=Q.front();Q.pop();for(int i=0;i<G[x].size();i++){int y=G[x][i].to;int diss=G[x][i].dis;dis[y]=max(dis[y],dis[x]+diss);if (--in[y]==0)Q.push(y);}} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,dis;scanf("%d%d%d",&x,&y,&dis);G[x].push_back(Node(y,dis));in[y]++;}getPath();int res=-INF;for(int i=0;i<n;i++)res=max(res,dis[i]);printf("%d\n",res);return 0; }

【例題】

• Instrction Arrangement（HDU-4109）(求關鍵路徑長度)：點擊這里

總結

以上是生活随笔為你收集整理的图论 —— AOE 网与关键路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。