算法:求解AOE网的关键路径

前面我们简要地介绍了AOE网和关键路径的一些概念,本文接着对求解关键路径程序的主要函数进行分析。现有一AOE网图如图7-9-4所示,我们使用邻接表存储结构,注意与拓扑排序时邻接表结构不同的地方在于,这里弧表结点增加了weight域,用来存储弧的权值。

求解事件的最早发生时间etv的过程,就是我们从头至尾找拓扑序列的过程,因此在求关键路径之前,需要先调用一次拓扑序列算法的代码来计算etv 和 拓扑序列列表,我们针对前面讲过的AOV网与拓扑排序的程序进行改进,代码如下(参考《大话数据结构》):

/* 拓扑排序,若GL无回路,则输出拓扑排序序列并返回1,若有回路返回0。 */
bool TopologicalSort(GraphAdjList GL)
{
    EdgeNode *pe;
    int i, k, gettop;
    int top = 0;/* 用于栈指针下标  */
    int count = 0;/* 用于统计输出顶点的个数  */
    /* 建栈将入度为0的顶点入栈  */
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));

    for (i = 0; i < GL->numVertexes; i++)
        if (0 == GL->adjList[i].in)
            stack[++top] = i;/* 将入度为0的顶点入栈 */

    top2 = 0;
    etv = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
        etv[i] = 0; /* 初始化 */
    stack2 = (int *)malloc(GL->numVertexes * sizeof(int));

    cout << "TopologicalSort ..." << endl;

    while (top != 0)
    {
        gettop = stack[top--];
        cout << GL->adjList[gettop].data << " -> ";
        count++;  /* 输出i号顶点,并计数 */

        stack2[++top2] = gettop; /* 将弹出的顶点序号压入拓扑序列的栈 */

        for (pe = GL->adjList[gettop].firstedge; pe; pe = pe->next)
        {
            k = pe->adjvex;
            /* 将i号顶点的邻接点的入度减1,如果减1后为0,则入栈 */
            if (!(--GL->adjList[k].in))
                stack[++top] = k;
            /* 求各顶点事件的最早发生时间etv值 */
            if ((etv[gettop] + pe->weight) > etv[k])
                etv[k] = etv[gettop] + pe->weight;
        }
    }
    cout << endl;
    if (count < GL->numVertexes)
        return false;
    else
        return true;
}

在程序开始处我们声明了几个全局变量:

int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组,全局变量 */ int *stack2;   /* 用于存储拓扑序列的栈 */ int top2;   /* 用于stack2的指针 */

其中stack2用来存储拓扑序列,以便后面求关键路径时使用。

上面的拓扑排序函数中除了增加了第12~19行,29行,38~39行,其他跟前面讲过的AOV网与拓扑排序没什么区别。

第12~19行初始化全局变量etv数组、top2和stack2的过程。第29行就是将本来要输出的拓扑序列压入全局栈stack2中。第38~39行很关键,是求etv数组的每一个元素的值,具体求值办法参见AOE网和关键路径

下面来看求关键路径的算法代码。

/* 求关键路径,GL为有向网,输出G的各项关键活动 */
void CriticalPath(GraphAdjList GL)
{
    EdgeNode *pe;
    int i, j, k, gettop;
    int ete, lte;/* 声明活动最早发生时间和最迟发生时间变量 */
    TopologicalSort(GL);/* 求拓扑序列,计算数组etv和stack2的值 */

    ltv = (int *)malloc(GL->numVertexes * sizeof(int)); /* 事件最早发生时间数组 */

    for (i = 0; i < GL->numVertexes; i++)
        ltv[i] = etv[GL->numVertexes - 1];/* 初始化 */

    cout << "etv :  ";
    for (i = 0; i < GL->numVertexes; i++)
        cout << etv[i] << ' ';
    cout << endl;

    while (top2 != 0)/* 出栈是求ltv */
    {
        gettop = stack2[top2--];
        /* 求各顶点事件的最迟发生时间ltv值 */
        for (pe = GL->adjList[gettop].firstedge; pe; pe = pe->next)
        {
            k = pe->adjvex;
            if (ltv[k] - pe->weight < ltv[gettop])
                ltv[gettop] = ltv[k] - pe->weight;
        }
    }

    cout << "ltv :  ";
    for (i = 0; i < GL->numVertexes; i++)
        cout << ltv[i] << ' ';
    cout << endl;
    /* 求ete,lte和关键活动 */
    for (j = 0; j < GL->numVertexes; j++)
    {
        for (pe = GL->adjList[j].firstedge; pe; pe = pe->next)
        {
            k = pe->adjvex;
            ete = etv[j];/* 活动最早发生时间 */
            lte = ltv[k] - pe->weight;/* 活动最迟发生时间 */
            if (ete == lte) /* 两者相等即在关键路径上 */
                cout << "<v" << GL->adjList[j].data << " - v"
                     << GL->adjList[k].data << "> length: " << pe->weight << endl;
        }
    }
}

函数第7行调用求拓扑序列的函数,执行完毕后,全局数组etv和栈stack2 如图7-9-6所示,top2 = 10,也就是说,对于每个事件的最早发生时间,我们已经计算出来了。

第11~12行初始化全局变量ltv数组,因为etv[9] = 27,所以数组ltv值现在为全27。

第19~29行是计算ltv 数组的循环,具体方法参见AOE网和关键路径

当程序执行到第36行,etv和ltv数组的值如图7-9-9

比如etv[1] = 3, 而ltv[1] = 7,表示如果单位是天的话,哪怕v1整个事件在第7天才开始,也可以保证整个工程的按期完成,可以提前v1事件开始时间,但最早也得第3天开始。

第36~47行是求另两个变量,活动最早开始时间ete和活动最晚开始时间lte,并对相同下标的它们进行比较。两重循环嵌套是对邻接表的顶点和每个顶点的弧表遍历,具体方法参见AOE网和关键路径,举例来说,如图7-9-10,当j = 0时,当k = 2, ete = lte, 表示

弧<v0, v2> 是关键路径,因此打印;当k = 1, ete != lte, 故弧<v0, v1> 不是关键路径。

j = 1 一直到 j = 9为止,做法是完全相同的,最后输出的结果如下图,最终关键路径如图7-9-11所示。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

Julia语言初体验

最近MIT发布的julia 1.0.0版,据传整合了C、Python、R等诸多语言特色,是数据科学领域又一把顶级利器。

2.3K2
来自专栏云计算教程系列

如何在Python 3中安装pandas包和使用数据结构

Python pandas包用于数据操作和分析,旨在让您以更直观的方式处理标记或关系数据。

2.1K0
来自专栏TechBox

一份走心的iOS开发规范前言约定(一)命名规范(二)编码规范2.14 内存管理规范本文参考文章其他有价值的文章

5268
来自专栏专注 Java 基础分享

Java 8 的时间日期 API

3754
来自专栏Spark学习技巧

重要 : 优化flink的四种方式

flink这个框架在逐步变为流处理的主流。本文,我们将针对flink性能调优讲四种不同的方法。

3312
来自专栏云霄雨霁

动态联通性问题----union-find算法

1980
来自专栏xingoo, 一个梦想做发明家的程序员

共享栈

共享栈,即是两个栈使用同一段存储空间。 第一个栈从数组头开始存储,第二个栈从数组尾开始,两个栈向中间拓展。 当top1+1==top2或者top1==top2-...

2427
来自专栏数据小魔方

左手用R右手Python系列之——noSQL基础与mongodb入门

12月的第一天,祝所有小伙伴儿的12月都能够被温柔以待。 能在学校悠哉写推送的日子所剩不多了,为了珍惜剩下所剩不多的推送机会,打算12月写一些实践性强一些的内...

5517
来自专栏程序员宝库

移除注释的完善思路:真的可以用正则实现?

网上有很多自称能实现移除JS注释的正则表达式,实际上存在种种缺陷。这使人多少有些愕然,也不禁疑惑到:真的可以用正则实现吗?而本篇文章以使用正则移除JS注释为目标...

1303
来自专栏非典型技术宅

Swift实践:使用CoreData存储多种数据类的通讯录1. CoreData支持存储数据类型2. 使用CoreData存储多种数据类的通讯录3. Codable

1863

扫码关注云+社区

领取腾讯云代金券