关键路径

AOE网（Activity on Edge）：它是一个带权的有向无环图，可用来估算工程的完成时间。

以下图为例。绿色的0叫做源点，红色的7叫做汇点；其他的每一个点都叫做一个事件；一条边叫做一项活动，权代表活动持续的时间。

其中，路径最长的路径叫做关键路径，影响工程进度的活动叫关键活动，并且关键路径上的活动一定是关键活动。

最早开工时间和最晚开工时间相等的工程是关键活动。

【问题描述】假设以AOE网表示一个施工流程图，弧上的权值表示完成该项子工程所需的时间。求：

① 完成整个工程的最短时间；

② 在满足依赖关系，并且不影响最短时间的前提下，每项工程的最早开工时间和最晚开工时间；

③ 关键路径

问题①、③以问题②为基础，比较容易实现。所以下面两个程序将解决问题②。

(1) 对DAG求关键路径  [邻接矩阵/邻接表]

这是DAG上的动态规划。注意，只有图的拓扑排序序列为0,1,2,……时才能用这种算法！

1. 状态表示：设 f(i)为事件 i 的最早开工时间，g(i)为事件 i 的最晚开工时间。

2. 状态转移方程：

f(i)＝min{f(j)＋G[j][i]} g(j)＝min{g(j)－G[j][i]} 其中 j 是 i 的前趋。

3. 边界条件：f(0)＝0，g(n)＝f(n－1)

4. 计算时先顺推出 f(n)，然后令 g(n)＝f(n)，再倒推出 g(0)。如果关键路径通过点 i，则 f(i)＝g(i)。

f[0]=0;

for (int i=1; i<=n; i++)

{

int max=0;

for (int j=0; j<=n; j++)

if (G[j]!=INF)   if (G[j]+f[j]>max) max=G[j]+f[j]; f=max;

}

g[n]=f[n]; for (int i=n-1; i>=0; i--) {  int min=INF;  for (int j=0; j<=n; j++)   if (G[j]!=INF)    if (g[j]-G[j]<min) min=g[j]-G[j];  g=min; } // 寻找关键路径 for (int i=1; i<n; i++) if (et==eet) cout<<i<<"->"; cout<<n;

(2) 对拓扑序列求关键路径  [邻接矩阵]

这仍然需要动态规划。

1. 划分阶段：以拓扑序列划分阶段，一项工程为一个阶段。

2. 状态表示：设 f(i)为事件 i 的最早开工时间，g(i)为事件 i 的最晚开工时间。

3. 状态转移方程：

f(i)＝min{f(j)＋G[j][i]} g(j)＝min{g(j)－G[j][i]} 其中 j＜i。由于序列由拓扑排序产生，j要么是i的前趋，要么和i无依赖关系。计算时先顺推出 f(n)，然后令 g(n)＝f(n)，再倒推出 g(0)。

#include <iostream> #include <cstring> using namespace std; const int INF=100000000, N=10000; int G[N][N]; int a[N];    // 拓扑排序序列 int f[N],g[N],prev[N]; int n,m; bool topsort();  // 拓扑排序，代码见153页，但是所有“<n”要改成“<=n”。 void print(int i) {  if (i==-1) return;  print(prev);  cout<<i<<" "; }

int main() {  cin>>n>>m;  for (int i=0; i<=n; i++)   for (int j=0; j<=n; j++)    G[j]=INF; for (int i=1; i<=m; i++) {   int u,v,w;   cin>>u>>v>>w;   G[v]=w; } memset(f,0,sizeof(f));  memset(g,0,sizeof(g));  memset(prev,-1,sizeof(prev));  if (!topsort()) return 0;   for (int i=1; i<=n; i++)   for (int j=0; j<i; j++)   {    int &x=a[j], &y=a;    if (G[x][y]!=INF && f[y]<f[x]+G[x][y])    {     f[y]=f[x]+G[x][y];     prev[y]=x;    }   } g[n]=f[n];  for (int i=n-1; i>=0; i--)   for (int j=n; j>i; j--)   {    int &x=a[j], &y=a;    if (G[y][x]!=INF && g[y]<g[x]-G[y][x])     g[y]=g[x]-G[y][x];   }   cout<<"Len="<<f[a[n]]<<endl;  print(a[n]);  return 0; }