数据结构 关键路径

　　如果在有向无环图中用有向边表示一个工程中的各项活动（Activity），用有向边上的权值表示活动的持续时间（duration），用顶点表示事件（Event），则这种有向图叫做用边表示活动的网络（activity on edges），简称AOE网络。例如：

　　

　　其中，E_i表示事件，a_k表示活动。E₀是源点，E₈是汇点。

 

　　完成整个工程所需的时间等于从源点到汇点的最长路径长度，即该路径中所有活动的持续时间之和最大。这条路径称为关键路径（critical path）。关键路径上所有活动都是关键活动。所谓关键活动（critical activity），是不按期完成会影响整个工程进度的活动。只要找到关键活动，就可以找到关键路径。

　　与计算关键活动有关的量：

　　1 事件E_i的最早可能开始时间：Ee[i]—从源点E₀到顶点E_i的最长路径长度。在上图中，Ee[4]=7。

　　2 事件E_i的最迟允许开始时间：El(小写L)[i]—在保证汇点E_n-1最迟允许开始时间El[n-1]等于整个工程所需时间的前提下，等于El[n-1]减去从E_i到E_n-1的最长路径长度。

　　3 活动a_k的最早可能开始时间：e[k]—设该活动在有向边<E_i，E_j>上，从源点E₀到顶点E_i的最长路径长度，即等于Ee[i]。

　　4 活动a_k的最迟允许开始时间：l(小写L)[k]—设该活动在有向边<E_i，E_j>上，在不会引起时间延误的前提下，允许的最迟开始时间。l[k]=El[j]-dur(<E_i，E_j>)，其中dur(<E_i，E_j>)是完成该活动所需的时间，即有向边<E_i，E_j>的权值。

　　l[k]-e[k]表示活动a_k的最早可能开始时间和最迟允许开始时间的时间余量，也叫做松弛时间（slack time）。没有时间余量的活动是关键活动。

　　算法步骤：

　　1 输入顶点数和边数，再输入每条边的起点编号、终点编号和权值。根据边的信息，通过一维数组存储每个顶点的入度和出度，建立邻接表保存边。每个顶点的Ee[i]设为0，El[i]设为100000000（表示无限大）。

　　2 按拓扑排序遍历所有顶点，更新Ee[i]。如果拓扑排序循环次数小于顶点数n，则说明网络中存在有向环，不能继续求关键路径。更新Ee[i]的最大值（整个工程所需时间）。

　　3 把所有汇点的最迟允许开始时间设为整个工程所需时间，按逆拓扑排序遍历所有顶点，更新El[i]。

　　4 通过DFS遍历所有边<E_i，E_j>。如果l[k]等于e[k]，则说明该活动是关键活动。依次输出关键活动上的顶点后构成关键路径。

　　在上图中，关键路径是a₁-a₄-a₇-a₁₀或a₁-a₄-a₈-a₁₁，完成整个工程所需时间是18。

 

　　题目 PTA 数据结构与算法题目集（中文） 7-11 关键活动（30 分）

　　多源点和多汇点例子：

11 14
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2
8 3 7
9 3 7
9 10 6
4 10 2
10 6 5
6 11 4

 

　　

　　结果如下：

21
3->4
4->10
6->11
8->3
9->3
10->6

　　C++代码如下：

//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct node
{
    int next, time;
};

int degree[2][110], t[2][110], maxtime;
vector<node> v[2][110];

int torder(int index, int n)
{
    int i;
    queue<int> q;

    for(i = 1; i <= n; i++)
    {
        if(degree[index][i] == 0)
        {
            if(index == 1)
            {
                t[1][i] = maxtime;
            }

            q.push(i);
        }
    }

    int cur, size, next, nexttime[2], curtime, count = 0;
    while(q.size() > 0)
    {
        cur = q.front();
        q.pop();

        count++;

        size = v[index][cur].size();
        for(i = 0; i < size; i++)
        {
            next = v[index][cur][i].next;
            degree[index][next]--;

            if(degree[index][next] == 0)
            {
                q.push(next);
            }

            curtime = t[index][cur];
            nexttime[0] = curtime + v[index][cur][i].time;
            nexttime[1] = curtime - v[index][cur][i].time;

            if(index == 0 && nexttime[0] > t[0][next])
            {
                t[0][next] = nexttime[0];
            }
            else if(index == 1 && nexttime[1] < t[1][next])
            {
                t[1][next] = nexttime[1];
            }
        }

        if(index == 0 && t[0][cur] > maxtime)
        {
            maxtime = t[0][cur];
        }
    }

    if(count < n)
    {
        return 0;
    }

    return 1;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    int i, a, b;
    node nod;

    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &nod.time);

        nod.next = b;
        v[0][a].push_back(nod);

        nod.next = a;
        v[1][b].push_back(nod);

        degree[1][a]++;
        degree[0][b]++;
    }

    for(i = 1; i <= n; i++)
    {
        t[0][i] = 0;
        t[1][i] = 100000000;
    }

    for(i = 0; i <= 1; i++)
    {
        if(torder(i, n) == 0)
        {
            printf("0\n");
            return 0;
        }
    }

    printf("%d\n", maxtime);

    int size, j, next;
    for(i = 1; i <= n; i++)
    {
        size = v[0][i].size();
        for(j = size - 1; j >= 0; j--)
        {
            next = v[0][i][j].next;
            if(t[1][next] - t[0][i] == v[0][i][j].time)
            {
                printf("%d->%d\n", i, next);
            }
        }
    }

    system("pause");
    return 0;
}

 

　　

 

　　参考资料

　　《图论算法理论、实现及应用》

　　06-图8. 关键活动（30）