AOE求关键路径
AOE
AOE图就是将节点作为事件，而中间的弧作为活动，权是活动持续的时间。
关键路径
在AOE图，一个事件发生的要求是通向其的活动全部结束，那么这么时间发生的最早时间就是与之相连的所有活动全部结束后的时间，而关键路径就是，使得事件都发生的路径。这个路径的时间一定是最长的。
基本思想
1.可以利用邻接矩阵的方式存储元素之间是否相连 2.在使用一个数组记录节点的入度 3.一个记录每个节点关键路径的字符串数组 首先判断入读和和出度为零的节点，分别记为tail，head。 将tail入队，然后，遍历以队首元素为tail的弧，若是不为无穷或则0，就将head的入度减一，知道入度为0就入队，直到队为空就结束。
实现代码
while(!all.empty()) //all为队列
{
int j=all.front();
all.pop();
for(int i=1;i<=a;i++)
{
if(p[j][i]!=9999)
{
if(v[j]+p[j][i]>v[i])
{v[i]=v[j]+p[j][i];
path[i]=path[j];
path[i].push_back(48+j);
}
l[i]--;
if(l[i]==0)
{
all.push(i); //入队就说明所有通过他的路径都以遍历结束，并且选出最长路径
}
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录