AOE网关键路径算法C++（结合拓扑排序）_aoe算法

AOE网

AOE即用边来表示活动，点表示事件的网，为有向无环图。
只有进入顶点之前的活动全部完成后，才可以开始当前事件。

关键路径

完成整个工程所需的最短时间取决于从起点到终点中，具有最长路径长度的路径，这条路径即为关键路径。

求解过程

先求出每个事件（顶点）的最早开始时间（etv）和最晚开始时间（ltv），再根据这个顺序求得每个活动（边）的最早开始时间（ete）和最晚开始时间（lte），ete = lte 的活动即为关键活动。
先初始化etv[ ] = {0};
etv[ i ] = max{ (etv[ i -1] + w< i-1, i >), etv[ i ] };
初始化 ltv[ ] = { etv[n] };
ltv[ i ] = min{ (ltv[i + 1] - w< i+1, i >), ltv[ i ] };

ete[ i ] = etv [ i ];
lte [ i ] = ltv[ i + 1 ] - w< i, i+1>;
公式理解
etv：每个顶点的最早发生时间，前一个事件结束后触发该事件，所以要根据前一个事件最早发生时间加上活动的时间，与当前存储的最早发生时间来比较，要保证所有前驱活动都完成才能开始，所以选择最大的，也就是相对最晚的。
ltv：每个顶点的最晚发生时间，应该是保证所有后继活动都能完成的情况下，使得耗时最长的后继活动刚好完成。用后继事件的最晚发生事件减去活动耗时，即为当前事件的最晚发生时间，选择相对较大的，才能保证后继活动全部都能完成。
ete：活动的最早开始时间应该是和前驱事件的最早发生时间相等。
lte：活动的最晚开始时间，为它后继事件的最晚发生时间减去活动时间，因为活动最晚开始，完成活动后，得到事件即为最晚发生。

拓扑排序
拓扑排序可以得到所有事件的发生顺序，可以保证得到的序列中，每个顶点不会受之后的顶点影响，按照拓扑序列的正序和反序，使得对当前结点求etv和ltv时，前驱和后继都已经确定了数据。

代码

//输入示例
// 6 7  0 1 2 3 4 5  0 1 1  0 2 3  0 4 3  1 3 4  2 3 1  3 5 5  3 4 3
#include<iostream>
#include <stack>

using namespace std;

#define MAXVEX 100

int* etv, * ltv;  //事件的最早和最晚发生时间
int top2;
stack<int> stack2;

//拓扑排序用到的图与普通图结构不同，这里是有向图，且要有存储结点入度数的变量
typedef struct EdgeNode  //出边表
{
	int adjvex;  //出边顶点
	int weight;  //权重
	struct EdgeNode* next;
}EdgeNode;

typedef struct VertexNode  //顶点表
{
	int in = 0;  //入度
	int data;  //值
	EdgeNode* firstedge;  //顶点出边
}VertexNode, Adjlist[MAXVEX];

typedef struct  //有向图
{
	Adjlist adjlist;  //顶点序列
	int numVex, numEdge;
}graphAdjlist, * GraphAdjlist;


void CreatGraph(graphAdjlist& G)
{
	int f, t, w;
	cout << "输入顶点数，边数" << endl;
	cin >> G.numVex >> G.numEdge;

	cout << "输入各顶点值" << endl;
	for (int i = 0; i < G.numVex; i++)
	{
		G.adjlist[i].in = 0;
		cin >> G.adjlist[i].data;
		G.adjlist[i].firstedge = nullptr;
	}
	cout << "输入各边，from to weight" << endl;

	for (int i = 0; i < G.numEdge; i++)  //输入边
	{
		cin >> f >> t >> w;
		EdgeNode* p;  //头插法
		p = new EdgeNode();
		p->adjvex = t;
		p->weight = w;
		p->next = G.adjlist[f].firstedge;
		G.adjlist[f].firstedge = p;
		G.adjlist[t].in++;
	}
}

void TopuSort(graphAdjlist G)  //先用拓扑排序求得拓扑序列以及活动最早发生时间
{
	stack<int> inVex;
	int top;
	int count = 0;
	int k;
	EdgeNode* e;
	for (int i = 0; i < G.numVex; i++)  //所有入度为0的点入栈
		if (G.adjlist[i].in == 0)
			inVex.push(i);

	// 初始化求事件最早发生时间相关数据
	top2 = 0;
	etv = (int*)malloc(MAXVEX * sizeof(int));
	for (int i = 0; i < G.numVex; i++)
		etv[i] = 0;

	while (!inVex.empty())  //栈不为空则
	{
		top = inVex.top();  //弹出栈顶
		inVex.pop();
		cout << G.adjlist[top].data << " ";  //输出栈顶
		count++;  //记录已生成序列总顶点数

		stack2.push(top); //对弹出的顶点序号压入栈，用于后续求最晚开始时间逆推

		//对弹出顶点遍历所有邻接点，入度-1，若-1后入度为0则入栈
		for (e = G.adjlist[top].firstedge; e != NULL; e = e->next)
		{
			k = e->adjvex;
			if ((--G.adjlist[k].in) == 0)
				inVex.push(k);

			//若前一个顶点的最早开始时间加上活动耗时，大于当前顶点的最早开始时间，更新
			if (etv[top] + e->weight > etv[k])  
				etv[k] = etv[top] + e->weight;
		}
	}
	if (count < G.numVex) //拓扑序列数小于顶点总数则说明有环
		cout << endl << "有环" << endl;
}

void CrticalPath(graphAdjlist G)
{
	int ete, lte;  //活动的最早和最晚发生时间
	int top,k ;
	EdgeNode* e;
	ltv= (int*)malloc(MAXVEX * sizeof(int));
	for (int i = 0; i < G.numVex; i++)
		ltv[i] = etv[G.numVex-1];
	while (!stack2.empty())
	{
		top = stack2.top();
		stack2.pop();
		for (e = G.adjlist[top].firstedge; e; e = e->next)
		{
			k = e->adjvex;
			if (ltv[k] - e->weight < ltv[top])
				ltv[top] = ltv[k] - e->weight;
		}
	}

	//下求ete和lte和关键活动
	cout << "关键活动：" << endl;
	for (int j = 0; j < G.numVex; j++)
	{
		for (e = G.adjlist[j].firstedge; e; e = e->next)
		{
			k = e->adjvex;
			ete = etv[j];
			lte = ltv[k] - e->weight;
			if (ete == lte)
				cout << "<" << j << "," << k << ">" << e->weight << "，";
		}
	}
}

int main()
{
	graphAdjlist G;
	CreatGraph(G);
	TopuSort(G);
	CrticalPath(G);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149