欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AOE-网的关键路径

程序员文章站 2022-06-20 09:03:47
...

AOE-网
边表示活动的有向无环网
AOE-网的相关概念
从源点到汇点的最长路径的长度为整个任务的所需时间,该路径称为关键路径
1、事件vi的最早发生时间ve(i):
ve(i) = max{ve(i.preVex) + Arc(i.preVex->i)}
2、事件vi的最晚发生时间vl(i):
vl(i) = min{vl(i.postVex) + Arc(i->i.postVex)}
3、活动a<j,k>的最早开始时间e(i)
e(i) = ve(j)
4、活动a<j,k>的最迟开始时间i(i)
l(i) = vl(k) - weight<j,k>
关键路径算法利用了 e(i) = l(i)
ve[]算法

for (int i = 0; i < VEXNUM; i++) {  // 在拓扑排序算法中求解ve[]
    if (arcs[x0][i] == 1){
        if (ve[x0] + arcs[x0][i] > ve[i]){  // 更新ve[]
            ve[i] = ve[x0] + arcs[x0][i];
        }
        indegree[i]--;
        if (indegree[i] == 0){
            stack.push(vexs[i]);
        }
    }
}

vl[]算法

vl = ve.clone();    // 求解vl[]
for (int x0 = VEXNUM-1; x0 > 0; x0--) {
    for (int j = 0; j < VEXNUM; j++) {
        if (arcs[x0][j] != 0){
            if (vl[j] - arcs[x0][j] > vl[x0]){  // 更新vl[]
                vl[x0] = vl[j] - arcs[x0][j];
            }
        }
    }
}

e[]和l[]算法(无代码)

/*
* 1、创建边集合的数组
* 2、对边集合的数组排序
* 3、根据每条边的邻接顶点找到ve[]和vl[]对应的e[]和v[]的值
* */
相关标签: Graph