AOE网与关键路径#

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动持续的时间，称这样的有向图为边表示活动的网，简称 AOE网(activity on edge network)。AOE网中没有入边的顶点称为源点，没有出边的顶点称为终点。AOE网具有以下两个性质：

只有在进入某顶点的各种活动都已经结束，该顶点表示的事件才能发生。
只有在某顶点所代表的事件发生后，从该顶点出发的活动才能开始。

如果用AOE网络来表示一项工程，那么，仅仅考虑各个活动之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；那些活动延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。

由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度（这里的路径长度是指该路径上的各个活动所持续的时间之和）。具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。关键路径长度是整个工程所需的最短工期。也就是说，要缩短整个工期，必须加快关键活动的进度。

关键路径算法#

想要找到关键路径，需要计算四组数据，①事件的最早发生时间，②事件的最晚发生时间，③活动 $a_i$ 的最早开始时间，④活动 $a_i$ 的最晚结束时间。当存在 $a_i的最在开始时间 = a_i最晚结束时间$ 时， $a_i$ 就包含在关键路径里面。

事件最早发生时间 ve[k]#

ve[k] 是指源点到顶点 $v_k$ 的最大路径长度，这和长度决定了所有顶点从 $v_k$ 出发的活动可以开始的最早时间。具AOE网的性质，只有进入 $v_k$ 的所有活动 $<v_j, v_k>$ 都结束时， $v_k$ 代表的事件才能发生，而活动 $<v_j, v_k>$ 的最早结束时间为 $ve[j] + len<v_j, v_k>$ 。所计算的最早发生时间的方法如下：

$\begin{cases}ve[0]=0\\ve[k] = max\{ve[j] + len<v_j,v_k>\}\end{cases}$

也就是计算从源点到这个顶点的最长路径，跟最短路径算法思路一样。

局部代码：

1
// 事件最早发生时间
2
int* ve = utils_createArr(n,0);
3
// 把源点入队列
4
queue_push(v_queue, createSNode(0));
5
while(queue_getLen(v_queue))
6
{
7
    v = queue_pop(v_queue)->value;
8
    for(int i = 0; i < n; i ++)
9
    {
10
        if(g[v][i] != -1)
11
        {
12
            queue_push(v_queue, createSNode(i));
13
            // 当存在比现存时间更晚时，替换
14
            if(ve[v] + g[v][i] > ve[i] )
15
            {
16
                ve[i] = ve[v] + g[v][i];
17
            }
18
        }
19
    }
20
}

事件的最迟发生时间 vl[k]#

vl[k] 是指在不推迟整个工期的前提下，事件 $v_k$ 允许的最晚发生时间。有向边 $<v_k,v_j>$ 代表从 $v_k$ 出发的活动，为了不拖延整个工期， $v_k$ 发生的最迟事件必须保证不推迟从事件 $v_k$ 出发的活动 $<v_k, v_j>$ 的终点 $v_j$ 的最迟时间 vl [ j ] 。vl [ k ] 的计算方法如下：

$\begin{cases}vl[n-1]=ve[n-1]\\vk[k]=min\{vl[j]-len<v_k,v_j>\}\end{cases}$

也就是 $当前顶点的最迟发生时间=终点的最早发生时间-当前顶点到终点的最长路径$

局部代码：

1
// 事件最迟发生的时间
2
// 把初值赋为最大的时间，方便比较
3
int* vl = utils_createArr(n, ve[v]);
4
// 终点的最早结束时间等于最迟发生时间
5
vl[v] = ve[v];
6

7
// 把终点入队列，经过 上面运算，v指向AOE网终点
8
queue_push(v_queue, createSNode(v));
9
while(queue_getLen(v_queue))
10
{
11
    v = queue_pop(v_queue)->value;
12
    for(int i = 0; i < n; i ++)
13
    {
14
        if(g[i][v] != -1)
15
        {
16
            queue_push(v_queue, createSNode(i));
17
            // 当存在比现存时间更早时，替换
18
            if(vl[v] - g[i][v] < vl[i])
19
            {
20
                vl[i] = vl[v] - g[i][v];
21
            }
22
        }
23
    }
24
}

活动 $a_i$ 的最早开始时间 ee[i]#

若活动 $a_i$ 由有向边 $<v_k, v_j>$ 表示，根据AOE网的性质，只有事件 $v_k$ 发生了，活动 $a_i$ 才能开始。也就是说，活动 $a_i$ 的最早开始时间等于事件 $v_k$ 的最早发生事件。因此有：

$ee[i] = ve[k]$

局部代码：

1
/*
2
活动 ai 最早发生时间，i为从开始结点算起
3
从编号较低的结点到编号较高的结点
4
从指向编号较低的结点到指向编号较高的结点
5
*/
6
int* ee = utils_createArr(es, 0);
7
int* v_flag = utils_createArr(n, 1);
8
int ee_i = 0;
9

10
queue_push(v_queue, createSNode(0));
11
while(queue_getLen(v_queue))
12
{
13
    v = queue_pop(v_queue)->value;
14
    for(int i = 0; i < n; i ++)
15
    {
16
        if(g[v][i] != -1)
17
        {
18
            ee[ee_i++] = ve[v];
19
            if(v_flag[i])
20
            {
21
                queue_push(v_queue, createSNode(i));
22
                v_flag[i] = 0;
23
            }
24
        }
25
    }
26
}

活动 $a_i$ 的最晚开始时间 el[i]#

el [ i ] 是指在不推迟整个工期的前提下，活动 $a_i$ 必须开始的最晚时间。若 $a_i$ 由有向边 $<v_k, v_j>$ 表示，则 $a_i$ 的最晚开始时间要保证事件 $v_j$ 的最迟延后时间不能后拖。因此有：

$el[i] = vl[j] - len<v_k, v_j>$

局部代码：

1
/*
2
活动 ai 最迟发生时间
3
*/
4
int* el = utils_createArr(es, 0);
5
int el_i = 0;
6

7
v_flag = utils_createArr(n, 1);
8
queue_push(v_queue, createSNode(0));
9

10
while(queue_getLen(v_queue))
11
{
12
    v = queue_pop(v_queue)->value;
13
    for(int i = 0; i < n; i ++)
14
    {
15
        if(g[v][i] != -1)
16
        {
17
            el[el_i++] = vl[i] - g[v][i];
18
            if(v_flag[i])
19
            {
20
                queue_push(v_queue, createSNode(i));
21
                v_flag[i] = 0;
22
            }
23
        }
24
    }
25

26
}

完整代码实现和测试结果#

完整代码：

1
// 关键路径
2
/*
3
g：邻接矩阵
4
n：顶点个数
5
es：边的个数
6

7
return：返回关键路径邻接矩阵
8
*/
9
int** graph_criticalPath(int** g, int n, int es)
10
{
11

12
    // 队列
13
    Queue* v_queue = createQueue();
14
    // 用来记录顶点下标的变量
15
    int v;
16

17
    // 事件最早发生时间
18
    int* ve = utils_createArr(n,0);
19
    // 把源点入队列
20
    queue_push(v_queue, createSNode(0));
21
    while(queue_getLen(v_queue))
22
    {
23
        v = queue_pop(v_queue)->value;
24
        for(int i = 0; i < n; i ++)
25
        {
26
            if(g[v][i] != -1)
27
            {
28
                queue_push(v_queue, createSNode(i));
29
                // 当存在比现存时间更晚时，替换
30
                if(ve[v] + g[v][i] > ve[i] )
31
                {
32
                    ve[i] = ve[v] + g[v][i];
33
                }
34
            }
35
        }
36
    }
37

38
    // 事件最迟发生的时间
39
    // 把初值赋为最大的时间，方便比较
40
    int* vl = utils_createArr(n, ve[v]);
41
    // 终点的最早结束时间等于最迟发生时间
42
    vl[v] = ve[v];
43

44
    // 把终点入队列，经过 上面运算，v指向AOE网终点
45
    queue_push(v_queue, createSNode(v));
46
    while(queue_getLen(v_queue))
47
    {
48
        v = queue_pop(v_queue)->value;
49
        for(int i = 0; i < n; i ++)
50
        {
51
            if(g[i][v] != -1)
52
            {
53
                queue_push(v_queue, createSNode(i));
54
                // 当存在比现存时间更早时，替换
55
                if(vl[v] - g[i][v] < vl[i])
56
                {
57
                    vl[i] = vl[v] - g[i][v];
58
                }
59
            }
60
        }
61
    }
62

63
    /*
64
    活动 ai 最早发生时间，i为从开始结点算起
65
    从编号较低的结点到编号较高的结点
66
    从指向编号较低的结点到指向编号较高的结点
67
    */
68
    int* ee = utils_createArr(es, 0);
69
    int* v_flag = utils_createArr(n, 1);
70
    int ee_i = 0;
71

72
    queue_push(v_queue, createSNode(0));
73
    while(queue_getLen(v_queue))
74
    {
75
        v = queue_pop(v_queue)->value;
76
        for(int i = 0; i < n; i ++)
77
        {
78
            if(g[v][i] != -1)
79
            {
80
                ee[ee_i++] = ve[v];
81
                if(v_flag[i])
82
                {
83
                    queue_push(v_queue, createSNode(i));
84
                    v_flag[i] = 0;
85
                }
86
            }
87
        }
88
    }
89

90

91
    /*
92
    活动 ai 最迟发生时间
93
    */
94
    int* el = utils_createArr(es, 0);
95
    int el_i = 0;
96

97
    v_flag = utils_createArr(n, 1);
98
    queue_push(v_queue, createSNode(0));
99

100
    while(queue_getLen(v_queue))
101
    {
102
        v = queue_pop(v_queue)->value;
103
        for(int i = 0; i < n; i ++)
104
        {
105
            if(g[v][i] != -1)
106
            {
107
                el[el_i++] = vl[i] - g[v][i];
108
                if(v_flag[i])
109
                {
110
                    queue_push(v_queue, createSNode(i));
111
                    v_flag[i] = 0;
112
                }
113
            }
114
        }
115

116
    }
117

118
    // 创建一个没有边的邻接矩阵
119
    int** g_cp = utils_create2DArr(n,n,-1);
120
    // 记录已经计算边数，用来计算是否为关键路径
121
    int cp_i = 0;
122
    for(int i = 0; i < n; i ++)
123
    {
124
        for(int j = 0; j < n; j ++)
125
        {
126
            if(g[i][j] != -1)
127
            {
128
                if(el[cp_i] - ee[cp_i] == 0)
129
                {
130
                    // 当活动最早发生时间=最晚发生时间，此活动在关键路径上
131
                    g_cp[i][j] = g[i][j];
132
                }
133
                cp_i++;
134
            }
135
        }
136
    }
137

138
    return g_cp;
139
}

测试样例： 在这里插入图片描述

测试代码：

1
#define N 9
2
#define M 33
3

4
int main()
5
{
6
    // 边数组，i%3=0 表示起点；i%3=1 表示终点；i%3=2 表示权值
7
    int arr[M] = {0,1,6,0,2,4,0,3,5,1,4,1,2,4,1,3,5,2,4,6,9,4,7,7,5,7,4,6,8,2,7,8,4};
8
    int** g = graph_createArrInValue(N, -1);
9
    // 创建相关邻接矩阵
10
    graph_createAdjacencyMatrixByArrWithWeight(g,arr, M, 1);
11

12
    printf("原图邻接矩阵：\n");
13
    graph_print(g, N, "%3d ");
14

15
    int** g_cp = graph_criticalPath(g,N,M/3);
16
    printf("关键路径邻接矩阵：\n");
17
    graph_print(g_cp, N, "%3d ");
18
    return 0;
19
}

运行结果：

在这里插入图片描述

关键路径展示： 在这里插入图片描述

原文链接：CSDN

AOE网与关键路径#

关键路径算法#

事件最早发生时间 ve[k]#

事件的最迟发生时间 vl[k]#

活动 aia_iai​ 的最早开始时间 ee[i]#

活动 aia_iai​ 的最晚开始时间 el[i]#

完整代码实现和测试结果#

活动 $a_i$ 的最早开始时间 ee[i]#

活动 $a_i$ 的最晚开始时间 el[i]#