数据结构（C++）AOE求关键路径_#include using namespace std; const int

AOE图求关键路径，我们可以把他比作一个工程，后续的工程需要前面的工程做铺垫，等到前面的所有工作都结束之后才可以开展后续的工作，有向赋权图就可以完成这样的表示。从起点到终点的路径不只有一条，但是需要路径上全部的活动都完成后，整个工程才算结束。因此，完成整个工程所需的最短时间取决于从起点到终点的最长路径长度，即这条路径上所有活动持续时间之和。
这条路径长度最长的路径就是关键路径。
这副图就可以比作一个工程，v9 工程结束。

关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
关键活动：关键路径上的活动称为关键活动。

事件发生最早时间v[k]

事件发生的最早时间可以表示为从起点到k顶点的最长路径。

void setve()
{
	int visited[MaxSize];
	queue<int>q;
	q.push(1);
	for (int i = 1; i <= vertexNum; ++i)
	{
		ve[i] = 0;
		visited[i] = 0;
	}
	visited[1] = 1;
	while (!q.empty())
	{
		int k = q.front();
		q.pop();
		for (int i = 1; i <= vertexNum; ++i)
		{
			if (arc[k][i] != INF && ve[k] + arc[k][i] > ve[i])
			{
				ve[i] = ve[k] + arc[k][i];
				if (visited[i] == 0)
					q.push(i);
				visited[i] = 1;
			}
		}
	}
}
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

事件发生的最迟时间

通过最长时间我们得到的整个工程的用时之后，把他赋给最后一个点的vl，通过最后一个点向前推进，最迟时间是最后一个点减路径长度的最小值。

void setvl()
{
	queue<int>q;
	int visited[MaxSize];
	q.push(vertexNum);
	for (int i = 1; i <= vertexNum; ++i)
	{
		vl[i] = ve[vertexNum];
		visited[i] = 0;
	}
	while (!q.empty())
	{
		int k = q.front();
		q.pop();
		for (int i = 0; i < vertexNum; i++)
		{
			if (arc[i][k] != INF && vl[k] - arc[i][k] < vl[i])
			{
				vl[i] = vl[k] - arc[i][k];
				if (!visited[i])
				{
					q.push(i);
				}
				visited[i] = 1;
			}
		}
	}
}
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

活动开始的最早时间e[i]

该活动起点的ve值

void sete()
{
	for (int i = 1; i <= arcNum; ++i)
	{
		edge[i].e = ve[edge[i].from];
	}
}
1
2
3
4
5
6
7

活动的最晚开始时间

该活动的终点vl值减去路径长度。

void setl()
{
	for (int i = 1; i <= arcNum; ++i)
	{
		edge[i].e = ve[edge[i].from];
		edge[i].i = vl[edge[i].to] - arc[edge[i].from][edge[i].to];
	}
}
1
2
3
4
5
6
7
8

实现的全部代码

#include<iostream>
#include<queue>
using namespace std;
const int MaxSize = 20;
const int INF = 0x3f;
int ve[MaxSize];
int vl[MaxSize];
int e[MaxSize];
int l[MaxSize];
struct Edge
{
	int from;
	int to;
	int e;
	int i;
};
class Graph
{
	int arcNum;
	int vertexNum;
	int arc[MaxSize][MaxSize];
	Edge edge[MaxSize];
public:
	Graph(int n, int e)
	{
		arcNum = e;
		vertexNum = n;
		for (int i = 1; i <= vertexNum; ++i)
		{
			for (int j = 1; j <= vertexNum; ++j)
			{
				if (i == j)
					arc[i][j] = 0;
				else
					arc[i][j] = INF;
			}
		}
		for (int i = 1; i <= arcNum; ++i)
		{
			int a, b, v;
			cin >> a >> b >> v;
			arc[a][b] = v;
			edge[i].from = a;
			edge[i].to = b;
		}
	}
	void setve()
	{
		int visited[MaxSize];
		queue<int>q;
		q.push(1);
		for (int i = 1; i <= vertexNum; ++i)
		{
			ve[i] = 0;
			visited[i] = 0;
		}
		visited[1] = 1;
		while (!q.empty())
		{
			int k = q.front();
			q.pop();
			for (int i = 1; i <= vertexNum; ++i)
			{
				if (arc[k][i] != INF && ve[k] + arc[k][i] > ve[i])
				{
					ve[i] = ve[k] + arc[k][i];
					if (visited[i] == 0)
						q.push(i);
					visited[i] = 1;
				}
			}
		}
	}
	void setvl()
	{
		queue<int>q;
		int visited[MaxSize];
		q.push(vertexNum);
		for (int i = 1; i <= vertexNum; ++i)
		{
			vl[i] = ve[vertexNum];
			visited[i] = 0;
		}
		while (!q.empty())
		{
			int k = q.front();
			q.pop();
			for (int i = 0; i < vertexNum; i++)
			{
				if (arc[i][k] != INF && vl[k] - arc[i][k] < vl[i])
				{
					vl[i] = vl[k] - arc[i][k];
					if (!visited[i])
					{
						q.push(i);
					}
					visited[i] = 1;
				}
			}
		}
	}
	void sete()
	{
		for (int i = 1; i <= arcNum; ++i)
		{
			edge[i].e = ve[edge[i].from];
		}
	}
	void setl()
	{
		for (int i = 1; i <= arcNum; ++i)
		{
			edge[i].e = ve[edge[i].from];
			edge[i].i = vl[edge[i].to] - arc[edge[i].from][edge[i].to];
		}
	}
	void getPoint()
	{
		int count = 0;
		for (int i = 1; i <= arcNum; ++i)
		{
			if (edge[i].e == edge[i].i)
			{
				cout << "v" << edge[i].from << " ";
				count = i;
			}
		}
		cout << "v" << edge[count].to;
	}
};
int main()
{
	int n, ee;
	cin >> n >> ee;
	Graph G(n, ee);
	G.setve();
	G.setvl();
	G.sete();
	G.setl();
	G.getPoint();
	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