起因
我上网搜了很久，没有看见别人写的AOE算法，要么就是用C写的，看上去很复杂，也没搞清楚他们这样写的意义。又看到了一个不是用C写的，但是我看不懂他写的什么。最后决定自己实现一下。由于没有图，所以可能需要先理解AOE，再看实现过程。
PS：如果觉得对你有用的话请点个赞或者评论，给我一个鼓励。或者对Code觉得有意见的话，可以把问题写在下面。
应用
AOE关键路径算法的应用：能够合理安排工程顺序。
工程图
例图
PS：上图来自于https://www.jianshu.com/p/1857ed4d8128。里面有过程推导（写的也一般）。
存储结构
1.AOE：Activity on Edge，活动在边上。
2.在图的存储中，顶点表示状态，边表示活动。
3.我们的目的，是从起始状态-->终止状态。
目的
获得每一个活动的开始时间的范围
当该活动开始时间范围只有一个点：最早开始时间==最晚开始时间-->关键活动
从开始到结束，存在一条路径，路径上所有的活动都是关键活动，该路径为关键路径。
前置知识：拓扑排序，详情请见我另一篇博客（还没写）
核心思想
1.状态的最早实现时间。用vEarlist 存储
前置状态结束以后，才可以到达这个状态
- -->vEarlist[v] = max(vEarlist[v], vEarlist[u] + G[u][v])
2.状态的最迟实现时间。用vLatest存储
后面那个状态实现的最迟时间-活动时间（对时间提出要求，至少得在这个时间完成）
- -->vLatest[v] = min(vLatest[v], vLatest[u] - G[v][u])
3.活动的最早实现时间。用eEarlist存储
前面那个状态到达了，活动即可开始：前面状态的最早开始时间
- -->eEarlist[i] = vEarlist[活动前状态]
4.活动的最迟实现时间。用eLatest存储
后面那个状态到达的最迟时间-活动时间
- -->eLatest[i] = vLatest[活动后状态] - i活动的时间
代码中将活动的信息全部打包。
eEarlist，eLatest，花费时间expd，状态前后startV和endV
算法
1.先进行拓扑排序，获得拓扑序列。
2.依据拓扑序列，更新顶点状态：顶点最早开始时间
3.找到最终结束点的最早开始时间，更新vLatest的最终点
4.对拓扑排序的逆序，进行操作，找到其相邻边，更新vLatest
5.对所有活动 更新其最早开始时间-->顶点最早开始时间 更新其最迟开始时间-->后顶点最迟开始时间-时长 更新可休息时间-->最迟-最早 如果可休息时间为0-->pre[后].push_back(前)
6.从结尾开始进行DFS，获得关键路径
输入格式：N(顶点数），M（边数），源点，汇点。
M行，活动开始状态（顶点），活动结束状态（顶点），活动进行时间。
输出格式：
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node{
int eEarlist;
int eLatest;
int eDiff;
int expd;
int startV, endV;
};
void DFS(int u);
int G[510][510];
const int MAX = 0x7FFFFFFF;
vector<int> vEarlist, vLatest;//状态最早开始时间和最迟开始时间
vector<node> actvt;//活动记录
vector<int> topoSeq;//拓扑排序的序列
vector<int> inDegree;//入度（配合拓扑排序使用）
vector<vector<int> > path;//关键路径（可能不止一条）
vector<int> tempPath;//DFS作临时路径
vector<vector<int> > pre;//状态的父状态（通过某条活动a->b，则pre[b]=a（其中一条））
int N, M, startV, endV;
int main()
{
fill(G[0], G[0]+510*510, MAX);
cin >> N >> M >> startV >>endV;
vEarlist.resize(N); vLatest.resize(N);
actvt.resize(M);
inDegree.resize(N);
fill(inDegree.begin(), inDegree.end(), 0);
for(int i=0; i<M; i++){
int u, v, expd;
cin >> u >> v >> expd;
G[u][v] = expd;
actvt[i].expd = expd; actvt[i].startV = u; actvt[i].endV = v;
inDegree[v]++;
}
//1.先进行拓扑排序，获得拓扑序列
queue<int> q;
q.push(startV);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=0; i<N; i++){
if(G[u][i] != MAX){//存在这条路
inDegree[i]--;
if(inDegree[i]==0){
q.push(i);
}
}
}
topoSeq.push_back(u);
}
//2.依据拓扑序列，更新顶点状态：顶点最早开始时间
fill(vEarlist.begin(), vEarlist.end(), 0);
for(int i=0; i<topoSeq.size(); i++){
int u = topoSeq[i];
for(int j=0; j<N; j++){
if(G[u][j] != MAX && vEarlist[u] + G[u][j] > vEarlist[j]){
vEarlist[j] = vEarlist[u] + G[u][j];
}
}
}
//3.找到最终结束点的最早开始时间，更新vLatest的最终点
fill(vLatest.begin(), vLatest.end(), vEarlist[endV]);
//4.对拓扑排序的逆序，进行操作，找到其相邻边，更新vLatest
reverse(topoSeq.begin(), topoSeq.end());//直接改就行，因为用不到了
for(int i=0; i<N; i++){
int u = topoSeq[i];//此时为逆序，所以u在后
for(int j=0; j<N; j++){
if(G[j][u] != MAX && vLatest[u] - G[j][u] < vLatest[j]){//有到达u的点
vLatest[j] = vLatest[u] - G[j][u];
}
}
}
//5.对所有活动，更新其最早开始时间-->顶点最早开始时间
// 更新其最迟开始时间-->后顶点最迟开始时间-时长
// 更新可休息时间-->最迟-最早
// 如果可休息时间为0-->pre[后].push_back(前)
//
pre.resize(M);
for(int i=0; i<M; i++){
actvt[i].eEarlist = vEarlist[actvt[i].startV];
actvt[i].eLatest = vLatest[actvt[i].endV] - actvt[i].expd;
actvt[i].eDiff = actvt[i].eLatest - actvt[i].eEarlist;
if(actvt[i].eDiff == 0){
pre[actvt[i].endV].push_back(actvt[i].startV);
}
}
//6.对结尾进行DFS，获得关键路径
// DFS(endV);
// path存储路径
DFS(endV);
for(int i=0; i<path.size(); i++){
for(int j=path[i].size()-1; j>=0; j--){
if(j!=path[i].size()-1)cout << "-->";
cout << path[i][j];
}
cout << endl;
}
}
void DFS(int u)
{
tempPath.push_back(u);
if(u == startV){
path.push_back(tempPath);
tempPath.pop_back();
return;
}
for(int i=0; i<pre[u].size(); i++){
DFS(pre[u][i]);
}
tempPath.pop_back();
}
`
网友评论