# AOE 網和關鍵路徑 ## 概念 AOE（Activity On Edge）網指用帶權邊集表示活動（邊權表示活動完成需要的時間），用頂點表示事件的有向無環圖。 AOE 網的最長路徑稱為關鍵路徑。 ### AOV 轉化為 AOE 若給定 AOV 網各頂點活動所需時間，則可將 AOV 網轉換為 AOE 網：將 AOV 網中的每個頂點拆成兩個頂點，分別表示活動的起止，兩頂點用有向邊連接，邊權為活動所需時間，原 AOV 網中的邊邊權為0，再根據需要添加超級源點和超級匯點即可。 ## 最長路徑 對于沒有正環的圖（指源點可達的正環），則將所有邊的邊權稱-1，再用 Bellman-Ford 或 SPFA 算法求最短路徑長度，結果乘-1即可。 若圖中有正環，則最長路徑不存在。 ## 關鍵路徑 ```c++ int ve[maxv]; int vl[maxv]; // topological series stack<int> topOrder; // 拓撲排序，順便求 ve[] bool topologicalSort(){ queue<int> q; for(int i=0;i<n;i++){ if(inDegree[i]==0) q.push(i); } while(!q.empty()){ int u=q.front(); q.pop(); topOrder.push(u); for(int i=0;i<Adj[u];i++){ int v=Adj[u][i].v; inDegree[v]--; if(inDegree[v]==0) q.push(v); } // 用 v 的前序節點 u 的 ve[u] 更新 ve[v] if(ve[u]+Adj[u][i].cost>ve[v]) ve[v]=ve[u]+Adj[u][i].cost; } if(topOrder.size==n) return true; else return false; } int CriticalPath(){ memset(ve,0,sizeof(ve)); if(topologicalSort()==false) return -1; int maxLength=0; for(int i=0;i<n;i++){ if(ve[i]>maxLength){ maxLength=ve[i]; } } fill(v1,v1+n,maxLength); // 用匯點的值初始化 vl while(!topOrder.empty()){ int u=topOrder.top(); topOrder.pop(); for(int i=0;i<Adj[u].size();i++){ int v=Adj[u][i].v; // 用 u 的所有后繼節點 v 的 vl[v] 值來更新 vl[u] if(vl[v]-Adj[u][i].w<vl[u]) vl[u]=vl[v]-Adj[u][i].w; } } // 遍歷鄰接表的所有邊 for(int u=0;u<n;u++){ for(int i=0;i<Adj[u].size();i++){ int v=Adj[u][i].v; // 活動的最早開始時間和最遲開始時間 int e=ve[u],l=vl[v]-w; if(e==l) printf("%d->%d\n",u,v) } } return maxLength; // 返回關鍵路徑長度 } ```