AOE网/关键路径
完整可运行代码实现在最后
在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity），在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。
[以上] 引自百度百科
中文名 AOE网 形 式 图
外文名 Activity On Edge Network 目 的 描述和分析工程的计划和过程
总之，AOE网用于一项工程的计划与实施，常用于时间与顺序的安排。AOE网（Activity On Edge Network）用边表示活动，用顶点表示事件（活动的完成）。边是带权的，表示活动需要的时间。
要理解AOE网，首先来看DAG图:
有向无环图
[以下] 引自王道 计算机考研 --数据结构
DAG常考用来描述表达式
如图表达式，可以将该图进行简化，将相同用途的节点进行合并简化，例如圈出来的乘号等。
步骤
拓扑排序
AOV网: 用顶点表示活动的网(Activity On Vertex NexWork)
用DAG图表示工程，顶点表示活动，有向边表示出边顶点是入边顶点的前提，边是带权的，表示活动需要的时间。
拓扑排序就是找到做事的先后顺序
实现:
- 从AOV网中选择一个入度为0的顶点并输出
- 从网中删除该顶点和所有以它为起点的有向边。
- 重复直到当前的AOV网为空或不存在无前驱的顶点为止
逆拓扑排序其实就是拓扑排序的逆向输出
对一个AOV网，若采用以下步骤排序，就是逆拓扑排序
- 从网中选择一个没有后继的顶点
- 删除该顶点和所有以它为终点的有向边
- 重复直到网为空
关键活动与关键路径
在AOE网中，从源点到汇点最长的路径称为关键路径，在关键路径上的活动称为关键活动。
因为AOE网中的活动是可以并行进行的，所以整个工程的时间开销，其实是最长路径的时间开销。即关键路径制约整个工程的工期。
想象你正在策划一个活动，这个活动由许多步骤（或事件）组成，每个步骤之间都有一定的时间间隔。在你希望在最短的时间内完成整个活动的前提下，关键路径法就是帮助你找到哪些步骤是至关重要的，哪一个步骤的延迟会直接影响整个活动的完成时间。
1. 什么是“最早发生时间 ve(k)”？
最早发生时间 ve(k) 就是你能尽快开始某个步骤的时间。它告诉你从活动的开始到这个步骤完成，最长需要多久。这个时间基于之前的所有步骤完成的情况。用更直白的说法，就是：假设你从活动的起点开始，走到某个步骤，最早你能做这一步的时间。
- 源点的最早发生时间 ve(源点) = 0，因为活动一开始就是从这里开始。
- 对于其他步骤，如果有多个前置步骤，
最早发生时间
就是这些步骤中最长的一个完成时间加上当前步骤的耗时。数学上表示为：
ve(k)= max( ve(j) + 耗时 (j,k) )
2. 什么是“最迟发生时间 vl(k)”？
最迟发生时间 vl(k) 代表了你还能拖延多久才能完成某个步骤，而不影响整个活动的总完成时间。换句话说，就是你在不耽误活动总时长的前提下，这一步骤最后能完成的时间。
- 对于汇点（最后一个步骤）,它的最迟发生时间就是它的最早发生时间，也就是活动结束时的时间：
vl(汇点)=ve(汇点) - 对于其他步骤，最迟发生时间是指，如果后面的步骤需要这么多时间才能完成，你这个步骤必须在某个时刻完成才能不延误整个活动。数学上表示为：
vl(k)= min ( vl (j) − 耗时(k,j) )
3. 活动的“最早开始时间 e(i)”？
活动的最早开始时间是指某个活动开始的最早时间。假设活动是从某个步骤开始的，那么这个活动的最早开始时间就是起点步骤的最早发生时间。
例如，如果活动是从步骤k到步骤j的，活动的最早开始时间就等于步骤k的最早发生时间。也就是说：
e(i)=ve(k)
4. 活动的“最迟开始时间 l(i)”？
活动的最迟开始时间是指活动在最迟时间内能开始的时间。假设这个活动要到步骤j才结束，那么它的最迟开始时间就是结束步骤j的最迟发生时间减去活动的耗时。
例如，如果活动是从步骤k到步骤j的，活动的最迟开始时间就等于步骤j的最迟发生时间减去从k到j的耗时：
l(i) = vl(j) − 耗时 (k,j)
5. 关键路径的定义和确定
最后，关键路径上的活动是那些最早开始时间 e(i) 等于 最迟开始时间 l(i) 的活动。这些活动就是最重要的，任何一个活动的延迟都会导致整个项目延期。
步骤总结：
- 从源点开始：设定源点的最早发生时间 ve(源点) 为0，然后按照拓扑顺序（从前往后的顺序）计算其他所有事件的最早发生时间 ve(k)。
- 从汇点反向计算：设定汇点的最迟发生时间 vl(汇点) = ve(汇点)，然后按照拓扑逆序（从后往前的顺序）计算其他事件的最迟发生时间 vl(k)。
- 计算活动的最早开始时间：根据每个活动的起点事件的最早发生时间，得出每个活动的最早开始时间 e(i)。
- 计算活动的最迟开始时间：根据每个活动的终点事件的最迟发生时间，得出每个活动的最迟开始时间 l(i)。
- 找关键路径：那些最早开始时间 e(i) = 最迟开始时间 l(i) 的活动组成了关键路径，关键路径上的每个活动都是“关键活动”。任何延迟这些关键活动的时间，都会延误整个活动的完成。
注:
- 关键活动的缩短有上限：关键路径上的活动如果缩短到某个点，就不再是关键活动了，可能会导致新的关键路径出现。因此，不能无限制地缩短关键活动的时间。
- 多个关键路径的存在：如果项目有多条关键路径，仅仅加速一条路径上的活动并不能缩短整个项目的工期。你必须加速所有关键路径上的关键活动才能真正缩短项目总工期。
AOE网代码实现
我们使用邻接表作为存储结构结构
#include <iostream>#include <string>#include <map>#include <vector>#include <stack>#include <algorithm> // for max#define no 10000using namespace std; // 定义Node结构体struct Node { int index; // 边的目标顶点的索引 Node* next; // 下一条边的指针 int distance; // 边的权重（距离）}; // 定义vNode结构体struct vNode { string nickname; // 代号 Node* firstarc; // 指向该顶点的邻接链表的头指针}; // 定义图的结构体struct MGraph { vNode* vArray; // 顶点数组 int vexnum; // 顶点数 int arcnum; // 边数 int *indegree; // 入度数组};
初始化 ** 函数，为了方便预输入，我们用二维数组存储图，并转化为邻接表
void initG(MGraph &G) { G.vexnum = 13; G.arcnum = 15; string nicknames[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"}; G.vArray = new vNode[G.vexnum]; for (int i = 0; i < G.vexnum; i++) { G.vArray[i].firstarc = NULL; G.vArray[i].nickname = nicknames[i]; } int edges[13][13] = { {no, 5, no, no, no, no, no, no, no, no, no, no, no}, {no, no, 3, 4, no, no, no, no, no, no, no, no, no}, {no, no, no, no, 5, no, no, no, no, no, no, no, no}, {no, no, no, no, no, 7, no, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, 3, no, no, no, no, no}, {no, no, no, no, no, no, no, no, 4, no, no, no, no}, {no, no, no, no, no, no, no, no, no, 2, no, no, no}, {no, no, no, no, no, no, no, no, no, no, 6, 7, no}, {no, no, no, no, no, no, no, no, no, no, no, 2, no}, {no, no, no, no, no, no, no, no, no, no, no, no, 5}, {no, no, no, no, no, no, no, no, no, no, no, no, 7}, {no, no, no, no, no, no, no, no, no, no, no, no, no} }; G.indegree = new int[G.vexnum]; for (int i = 0; i < G.vexnum; i++) G.indegree[i] = 0; for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (edges[i][j] != no) { G.indegree[j]++; } } } for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (edges[i][j] != no) { Node* newNode = new Node{j, G.vArray[i].firstarc, edges[i][j]}; // 指针指向的是顶点 i 的邻接表中的第一个节点 G.vArray[i].firstarc = newNode; } } }}
然后是关键代码实现
bool TopologicalSort(MGraph &G) { // 定义两个数组，分别用于记录各顶点的最早发生时间和最晚发生时间 int *ve, *vl; ve = new int[G.vexnum]; // ve是最早发生时间数组，用来记录每个顶点的最早开始时间 vl = new int[G.vexnum]; // vl是最晚发生时间数组，用来记录每个顶点的最晚完成时间 // 初始化所有顶点的最早发生时间为0 fill(ve, ve + G.vexnum, 0); // 初始化所有顶点的最晚发生时间为一个较大的值 (no) fill(vl, vl + G.vexnum, no); stack<int> S; // 用栈来辅助存储入度为0的顶点 vector<int> print(G.vexnum, -1); // 用来保存拓扑排序的结果 int count = 0; // 记录已排序的顶点数 // 步骤 1: 初始化栈，将所有入度为0的顶点入栈 for (int i = 0; i < G.vexnum; i++) { if (G.indegree[i] == 0) { // 如果当前顶点的入度为0 S.push(i); // 将该顶点入栈，表示它可以开始 } } // 步骤 2: 开始进行拓扑排序 while (!S.empty()) { // 当栈不为空时 int u = S.top(); // 获取栈顶元素 S.pop(); // 弹出栈顶元素 print[count++] = u; // 将当前顶点加入拓扑排序结果数组，并增加排序计数 // 遍历与当前顶点u相邻的所有顶点 Node* p = G.vArray[u].firstarc; while (p != NULL) { // 遍历顶点u的所有邻接边 int v = p->index; // 获取邻接顶点v的索引 // 更新顶点v的入度，表示已经处理过了当前的边 G.indegree[v]--; if (G.indegree[v] == 0) { // 如果v的入度变为0，说明v可以开始 S.push(v); // 将v入栈 } // 更新顶点v的最早发生时间 ve[v] = max(ve[v], ve[u] + p->distance); // v的最早开始时间 = u(前驱)的最早时间 + 边的权重 p = p->next; // 移动到v的下一个邻接点 } } // 步骤 3: 检查是否存在环 if (count != G.vexnum) { // 如果拓扑排序的顶点数不等于图中顶点数，说明存在环 cout << "图中存在环，无法进行拓扑排序！" << endl; return false; } // 输出拓扑排序结果 cout << "拓扑排序结果：\n"; for (int i = 0; i < G.vexnum; i++) { if (print[i] != -1) { // 确保输出的顶点有效 cout << G.vArray[print[i]].nickname << " "; // 输出每个顶点的昵称 } } cout << endl; // 步骤 4: 输出各顶点的最早发生时间ve cout << "各顶点的最早发生时间 (ve):\n"; for (int i = 0; i < G.vexnum; i++) { cout << G.vArray[i].nickname << ": " << ve[i] << endl; // 输出每个顶点的最早发生时间 } // 步骤 5: 计算各顶点的最晚发生时间 // 首先，将所有顶点的最晚发生时间初始化为图中最后一个顶点的最早发生时间 for (int i = 0; i < G.vexnum; i++) { vl[i] = ve[G.vexnum - 1]; // 最晚时间初始化为图中最早完成时间的最大值 } // 然后，从后往前遍历拓扑排序的结果，计算最晚发生时间 for (int i = G.vexnum - 1; i >= 0; i--) { int u = print[i]; // 获取当前顶点u Node* p = G.vArray[u].firstarc; while (p != NULL) { // 遍历u的所有邻接顶点 int v = p->index; // 获取邻接顶点v的索引 // 更新u的最晚发生时间，vl[u] = min(vl[u], vl[v] - 边的权重) vl[u] = min(vl[u], vl[v] - p->distance); p = p->next; // 移动到下一个邻接点 } } // 输出各顶点的最晚发生时间vl cout << "各顶点的最晚发生时间 (vl):\n"; for (int i = 0; i < G.vexnum; i++) { cout << G.vArray[i].nickname << ": " << vl[i] << endl; // 输出每个顶点的最晚发生时间 } // 步骤 6: 计算并输出各顶点的关键路径 cout << "各顶点的关键路径：\n"; for (int i = 0; i < G.vexnum; i++) { Node* p = G.vArray[i].firstarc; while (p != NULL) { // 遍历每个顶点的邻接边 int v = p->index; // 获取邻接顶点v的索引 // 如果ve[u] == vl[v] - p->distance，说明u->v是关键路径的一部分 if (ve[i] == vl[v] - p->distance) { cout << G.vArray[i].nickname << "->" << G.vArray[v].nickname << " "; } p = p->next; // 移动到下一个邻接点 } } return true; }
输出结果如下:
完整代码:
#include <iostream>#include <string>#include <map>#include <vector>#include <stack>#include <algorithm> // for max#define no 10000using namespace std; // 定义Node结构体struct Node { int index; // 边的目标顶点的索引 Node* next; // 下一条边的指针 int distance; // 边的权重（距离）}; // 定义vNode结构体struct vNode { string nickname; // 代号 Node* firstarc; // 指向该顶点的邻接链表的头指针}; // 定义图的结构体struct MGraph { vNode* vArray; // 顶点数组 int vexnum; // 顶点数 int arcnum; // 边数 int *indegree; // 入度数组}; void initG(MGraph &G) { G.vexnum = 13; G.arcnum = 15; string nicknames[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"}; G.vArray = new vNode[G.vexnum]; for (int i = 0; i < G.vexnum; i++) { G.vArray[i].firstarc = NULL; G.vArray[i].nickname = nicknames[i]; } int edges[13][13] = { {no, 5, no, no, no, no, no, no, no, no, no, no, no}, {no, no, 3, 4, no, no, no, no, no, no, no, no, no}, {no, no, no, no, 5, no, no, no, no, no, no, no, no}, {no, no, no, no, no, 7, no, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, 3, no, no, no, no, no}, {no, no, no, no, no, no, no, no, 4, no, no, no, no}, {no, no, no, no, no, no, no, no, no, 2, no, no, no}, {no, no, no, no, no, no, no, no, no, no, 6, 7, no}, {no, no, no, no, no, no, no, no, no, no, no, 2, no}, {no, no, no, no, no, no, no, no, no, no, no, no, 5}, {no, no, no, no, no, no, no, no, no, no, no, no, 7}, {no, no, no, no, no, no, no, no, no, no, no, no, no} }; G.indegree = new int[G.vexnum]; for (int i = 0; i < G.vexnum; i++) G.indegree[i] = 0; for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (edges[i][j] != no) { G.indegree[j]++; } } } for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (edges[i][j] != no) { Node* newNode = new Node{j, G.vArray[i].firstarc, edges[i][j]}; // 指针指向的是顶点 i 的邻接表中的第一个节点 G.vArray[i].firstarc = newNode; } } }} bool TopologicalSort(MGraph &G) { // 定义两个数组，分别用于记录各顶点的最早发生时间和最晚发生时间 int *ve, *vl; ve = new int[G.vexnum]; // ve是最早发生时间数组，用来记录每个顶点的最早开始时间 vl = new int[G.vexnum]; // vl是最晚发生时间数组，用来记录每个顶点的最晚完成时间 // 初始化所有顶点的最早发生时间为0 fill(ve, ve + G.vexnum, 0); // 初始化所有顶点的最晚发生时间为一个较大的值 (no) fill(vl, vl + G.vexnum, no); stack<int> S; // 用栈来辅助存储入度为0的顶点 vector<int> print(G.vexnum, -1); // 用来保存拓扑排序的结果 int count = 0; // 记录已排序的顶点数 // 步骤 1: 初始化栈，将所有入度为0的顶点入栈 for (int i = 0; i < G.vexnum; i++) { if (G.indegree[i] == 0) { // 如果当前顶点的入度为0 S.push(i); // 将该顶点入栈，表示它可以开始 } } // 步骤 2: 开始进行拓扑排序 while (!S.empty()) { // 当栈不为空时 int u = S.top(); // 获取栈顶元素 S.pop(); // 弹出栈顶元素 print[count++] = u; // 将当前顶点加入拓扑排序结果数组，并增加排序计数 // 遍历与当前顶点u相邻的所有顶点 Node* p = G.vArray[u].firstarc; while (p != NULL) { // 遍历顶点u的所有邻接边 int v = p->index; // 获取邻接顶点v的索引 // 更新顶点v的入度，表示已经处理过了当前的边 G.indegree[v]--; if (G.indegree[v] == 0) { // 如果v的入度变为0，说明v可以开始 S.push(v); // 将v入栈 } // 更新顶点v的最早发生时间 ve[v] = max(ve[v], ve[u] + p->distance); // v的最早开始时间 = u(前驱)的最早时间 + 边的权重 p = p->next; // 移动到v的下一个邻接点 } } // 步骤 3: 检查是否存在环 if (count != G.vexnum) { // 如果拓扑排序的顶点数不等于图中顶点数，说明存在环 cout << "图中存在环，无法进行拓扑排序！" << endl; return false; } // 输出拓扑排序结果 cout << "拓扑排序结果：\n"; for (int i = 0; i < G.vexnum; i++) { if (print[i] != -1) { // 确保输出的顶点有效 cout << G.vArray[print[i]].nickname << " "; // 输出每个顶点的昵称 } } cout << endl; // 步骤 4: 输出各顶点的最早发生时间ve cout << "各顶点的最早发生时间 (ve):\n"; for (int i = 0; i < G.vexnum; i++) { cout << G.vArray[i].nickname << ": " << ve[i] << endl; // 输出每个顶点的最早发生时间 } // 步骤 5: 计算各顶点的最晚发生时间 // 首先，将所有顶点的最晚发生时间初始化为图中最后一个顶点的最早发生时间 for (int i = 0; i < G.vexnum; i++) { vl[i] = ve[G.vexnum - 1]; // 最晚时间初始化为图中最早完成时间的最大值 } // 然后，从后往前遍历拓扑排序的结果，计算最晚发生时间 for (int i = G.vexnum - 1; i >= 0; i--) { int u = print[i]; // 获取当前顶点u Node* p = G.vArray[u].firstarc; while (p != NULL) { // 遍历u的所有邻接顶点 int v = p->index; // 获取邻接顶点v的索引 // 更新u的最晚发生时间，vl[u] = min(vl[u], vl[v] - 边的权重) vl[u] = min(vl[u], vl[v] - p->distance); p = p->next; // 移动到下一个邻接点 } } // 输出各顶点的最晚发生时间vl cout << "各顶点的最晚发生时间 (vl):\n"; for (int i = 0; i < G.vexnum; i++) { cout << G.vArray[i].nickname << ": " << vl[i] << endl; // 输出每个顶点的最晚发生时间 } // 步骤 6: 计算并输出各顶点的关键路径 cout << "各顶点的关键路径：\n"; for (int i = 0; i < G.vexnum; i++) { Node* p = G.vArray[i].firstarc; while (p != NULL) { // 遍历每个顶点的邻接边 int v = p->index; // 获取邻接顶点v的索引 // 如果ve[u] == vl[v] - p->distance，说明u->v是关键路径的一部分 if (ve[i] == vl[v] - p->distance) { cout << G.vArray[i].nickname << "->" << G.vArray[v].nickname << " "; } p = p->next; // 移动到下一个邻接点 } } return true; } int main() { MGraph G; initG(G); if (!TopologicalSort(G)) { cout << "拓扑排序失败！" << endl; } return 0;}