数据结构 关键路径

时间:2022-05-24 09:31:23

  如果在有向无环图中用有向边表示一个工程中的各项活动(Activity),用有向边上的权值表示活动的持续时间(duration),用顶点表示事件(Event),则这种有向图叫做用边表示活动的网络(activity on edges),简称AOE网络。例如:

  数据结构 关键路径

  其中,Ei表示事件,ak表示活动。E0是源点,E8是汇点。

 

  完成整个工程所需的时间等于从源点到汇点的最长路径长度,即该路径中所有活动的持续时间之和最大。这条路径称为关键路径(critical path)。关键路径上所有活动都是关键活动。所谓关键活动(critical activity),是不按期完成会影响整个工程进度的活动。只要找到关键活动,就可以找到关键路径。

  与计算关键活动有关的量:

  1 事件Ei的最早可能开始时间:Ee[i]—从源点E0到顶点Ei的最长路径长度。在上图中,Ee[4]=7。

  2 事件Ei的最迟允许开始时间:El(小写L)[i]—在保证汇点En-1最迟允许开始时间El[n-1]等于整个工程所需时间的前提下,等于El[n-1]减去从Ei到En-1的最长路径长度。

  3 活动ak的最早可能开始时间:e[k]—设该活动在有向边<Ei,Ej>上,从源点E0到顶点Ei的最长路径长度,即等于Ee[i]。

  4 活动ak的最迟允许开始时间:l(小写L)[k]—设该活动在有向边<Ei,Ej>上,在不会引起时间延误的前提下,允许的最迟开始时间。l[k]=El[j]-dur(<Ei,Ej>),其中dur(<Ei,Ej>)是完成该活动所需的时间,即有向边<Ei,Ej>的权值。

  l[k]-e[k]表示活动ak最早可能开始时间和最迟允许开始时间的时间余量,也叫做松弛时间(slack time)。没有时间余量的活动是关键活动。

  算法步骤:

  1 输入顶点数和边数,再输入每条边的起点编号、终点编号和权值。根据边的信息,通过一维数组存储每个顶点的入度和出度,建立邻接表保存边。每个顶点的Ee[i]设为0,El[i]设为100000000(表示无限大)。

  2 按拓扑排序遍历所有顶点,更新Ee[i]。如果拓扑排序循环次数小于顶点数n,则说明网络中存在有向环,不能继续求关键路径。更新Ee[i]的最大值(整个工程所需时间)。

  3 把所有汇点的最迟允许开始时间设为整个工程所需时间,按逆拓扑排序遍历所有顶点,更新El[i]。

  4 通过DFS遍历所有边<Ei,Ej>。如果l[k]等于e[k],则说明该活动是关键活动。依次输出关键活动上的顶点后构成关键路径。

  在上图中,关键路径是a1-a4-a7-a10或a1-a4-a8-a11,完成整个工程所需时间是18。

 

  题目 PTA 数据结构与算法题目集(中文) 7-11 关键活动(30 分)

  多源点和多汇点例子:

 1 11 14
 2 1 2 4
 3 1 3 3
 4 2 4 5
 5 3 4 3
 6 4 5 1
 7 4 6 6
 8 5 7 5
 9 6 7 2
10 8 3 7
11 9 3 7
12 9 10 6
13 4 10 2
14 10 6 5
15 6 11 4

 

  数据结构 关键路径

  结果如下:

1 21
2 3->4
3 4->10
4 6->11
5 8->3
6 9->3
7 10->6

  C++代码如下:

数据结构 关键路径数据结构 关键路径
  1 //#include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 #include <queue>
  5 
  6 using namespace std;
  7 
  8 struct node
  9 {
 10     int next, time;
 11 };
 12 
 13 int degree[2][110], t[2][110], maxtime;
 14 vector<node> v[2][110];
 15 
 16 int torder(int index, int n)
 17 {
 18     int i;
 19     queue<int> q;
 20 
 21     for(i = 1; i <= n; i++)
 22     {
 23         if(degree[index][i] == 0)
 24         {
 25             if(index == 1)
 26             {
 27                 t[1][i] = maxtime;
 28             }
 29 
 30             q.push(i);
 31         }
 32     }
 33 
 34     int cur, size, next, nexttime[2], curtime, count = 0;
 35     while(q.size() > 0)
 36     {
 37         cur = q.front();
 38         q.pop();
 39 
 40         count++;
 41 
 42         size = v[index][cur].size();
 43         for(i = 0; i < size; i++)
 44         {
 45             next = v[index][cur][i].next;
 46             degree[index][next]--;
 47 
 48             if(degree[index][next] == 0)
 49             {
 50                 q.push(next);
 51             }
 52 
 53             curtime = t[index][cur];
 54             nexttime[0] = curtime + v[index][cur][i].time;
 55             nexttime[1] = curtime - v[index][cur][i].time;
 56 
 57             if(index == 0 && nexttime[0] > t[0][next])
 58             {
 59                 t[0][next] = nexttime[0];
 60             }
 61             else if(index == 1 && nexttime[1] < t[1][next])
 62             {
 63                 t[1][next] = nexttime[1];
 64             }
 65         }
 66 
 67         if(index == 0 && t[0][cur] > maxtime)
 68         {
 69             maxtime = t[0][cur];
 70         }
 71     }
 72 
 73     if(count < n)
 74     {
 75         return 0;
 76     }
 77 
 78     return 1;
 79 }
 80 
 81 int main()
 82 {
 83     int n, m;
 84     scanf("%d%d", &n, &m);
 85 
 86     int i, a, b;
 87     node nod;
 88 
 89     for(i = 1; i <= m; i++)
 90     {
 91         scanf("%d%d%d", &a, &b, &nod.time);
 92 
 93         nod.next = b;
 94         v[0][a].push_back(nod);
 95 
 96         nod.next = a;
 97         v[1][b].push_back(nod);
 98 
 99         degree[1][a]++;
100         degree[0][b]++;
101     }
102 
103     for(i = 1; i <= n; i++)
104     {
105         t[0][i] = 0;
106         t[1][i] = 100000000;
107     }
108 
109     for(i = 0; i <= 1; i++)
110     {
111         if(torder(i, n) == 0)
112         {
113             printf("0\n");
114             return 0;
115         }
116     }
117 
118     printf("%d\n", maxtime);
119 
120     int size, j, next;
121     for(i = 1; i <= n; i++)
122     {
123         size = v[0][i].size();
124         for(j = size - 1; j >= 0; j--)
125         {
126             next = v[0][i][j].next;
127             if(t[1][next] - t[0][i] == v[0][i][j].time)
128             {
129                 printf("%d->%d\n", i, next);
130             }
131         }
132     }
133 
134     system("pause");
135     return 0;
136 }
View Code

 

  数据结构 关键路径

 

  参考资料

  《图论算法理论、实现及应用》

  06-图8. 关键活动(30)