图——基本的图算法（四）关键路径

关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序，所以在这里先以拓扑排序开篇。

1． 什么是拓扑排序？
举个例子先：一个软件专业的学生学习一系列的课程，其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边表示先决条件。若课程i是课程j的先决条件，则图中有弧(i,j)。若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列，必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前，若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列，称之为拓扑序列。
2． 如何实现拓扑排序？
很简单，两个步骤：
1． 在有向图中选一个没有前驱的顶点且输出。
2． 从图中删除该顶点和以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
3． 什么是关键路径？
在学习关键路径前，先了解一个AOV网和AOE网的概念：

用顶点表示活动，用弧表示活动间的优先关系的有向图：
称为顶点表示活动的网（Activity On Vertex Network），简称为AOV网。
与AOV网对应的是AOE（Activity On Edge）网即边表示活动的网。
AOE网是一个带权的有向无环图。
网中只有一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。
其中，顶点表示事件（Event），弧表示活动，权表示活动持续的时间。
通常，AOE网可用来估算工程的完成时间。
假如汽车生产工厂要制造一辆汽车，制造过程的大概事件和活动时间如上图AOE网：
我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
那么，显然对上图AOE网而言,所谓关键路径：
开始–>发动机完成–>部件集中到位–>组装完成。路径长度为5.5。
如果我们试图缩短整个工期，去改进轮子的生产效率，哪怕改动0.1也是无益的。
只有缩短关键路径上的关键活动时间才可以减少整个工期的长度。
例如如果制造发动机缩短为2.5天，整车组装缩短为1.5天，那么关键路径为4.5。
工期也就整整缩短了一天时间。
好吧！ 那么研究这个关键路径意义何在？
假定上图AOE网中弧的权值单位为小时，而且我们已经知道黑深色的那一条为关键路径。
假定现在上午一点，对于外壳完成事件而言，为了不影响工期：
外壳完成活动最早也就是一点开始动工，最晚在两点必须要开始动工。
最大权值3表示所有活动必须在三小时之后完成，而外壳完成只需要2个小时。
所以，这个中间的空闲时间有一个小时，为了不影响整个工期，它必须最迟两点动工。
那么才可以保证3点时与发动机完成活动同时竣工，为后续的活动做好准备。
对AOE网有待研究的问题是：
（1）完成整个工程至少需要多少时间？
（2）那些活动是影响工程进度的关键？
今天研究是实例如下图所示：

假想是一个有11项活动的AOE网，其中有9个事件(V1,V2,V3…V9)。
每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。
如V1表示整个工程开始，V9表示整个共结束，V5表示a4和a5已经完成，a7和a8可以开始。
关键路径算法
为了更好的理解算法，我们先需要定义如下几个参数：
（1）事件的最早发生时间etv(earliest time of vertex): 即顶点Vk的最早发生时间。
（2）事件的最晚发生时间ltv(latest time of vertex): 即顶点Vk的最晚发生时间。也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
（3）活动的最早开工时间ete(earliest time of edge): 即弧ak的最早发生时间。
（4）活动的最晚开工时间lte(latest time of edge): 即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。
然后根据最早开工时间ete[k]和最晚开工时间lte[k]相等判断ak是否是关键路径。
将AOE网转化为邻接表结构如下图所示：

求事件 的最早发生时间etv的过程，就是我们从头至尾找拓扑序列的过程，因此，在求关键路径之前，需要先调用一次拓扑序列算法来计算etv和拓扑序列列表。为此我们首先在程序开始处声明几个全局变量。

int  *etv,*ltv;//事件最早发生时间和最迟发生时间数组
int  *stack2;//用于存储拓扑序列的栈
int   top2; //用于stack2的指针
//下面是改进过的求拓扑序列算法
status  TopologicalSort(GraphAdjList   GL)
{
      EdgeNode   *e;
      int   i,k,gettop;
      int   top=0;    //用于栈指针下标
      int    count=0;   //用于统计输出顶点的个数
      int     *stack;  //创栈将入度为0的顶点入栈
     stack=(int  *)malloc(GL->numVertexes*sizeof(int));
     for(i=0;i<GL->numVertexes;i++)
          if(0==GL->adjList[i].in) stack[++top]=i;
      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));
    while(top!=0)
    {
        gettop = stack[top--];
       count++;
       stack2[++top2] = gettop; //将弹出的顶点序号压入拓扑序列的栈
        for(e=GL->adjList[gettop].firstedge;e;e=e->next)
        {
                k=e->adjvex;
               if(!(--GL->adjList[k].in))
                       stack[++top]=k;
             if((etv[gettop]+e->weight)>etv[k])
                        etv[k]=etv[gettop]+e->weight;
         }
    }
        if(count<GL->numVertexes)
            return ERROR;
        else
            return OK;
}
 

第11~15行为初始化全局变量etv数组、top2和stack2的过程。第21行就是将本是要输出的拓扑序列压入全局栈stack2中。第27~28行很关键，它是求etv数组的每一个元素的值。比如说，假如我们已经求得顶点v0对应的etv[0]=0，顶点v1对应的etv[1]=3，顶点v2对应的etv[2]=4，现在我们需要求顶点v3对应的etv[3]，其实就是求etv[1]+len（v1,v3）与etv[2]+len（v2,v3）的较大值。显然3+5<4+8，得到etv[3]=12。如图所示，在代码中e->weight就是当前弧的长度。

下面我们来看一下求关键路径的算法代码
下面我们来看一下求关键路径的算法代码

void CriticalPath(GraphAdjList GL)

{
        EdgeNode   *e;
        int   i,gettop,k,j;
        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];//初始化ltv
       while(top2!=0)
       {
                 gettop = stack2[top2-1];
                 for(e=GL->adjList[gettop].firstedge;e;e=e->next)
                 {//求各顶点事件的最迟发生时间ltv值
                       k=e->adjvex;
                      if(ltv[k]-e->weight<ltv[gettop])//各点事件最晚发生时间
                           ltv[gettop] =ltv[k]-e->weight;
                 }
                  for(j=0;j<GL->numVertexes;j++)
                 {
                         for(e=GL->adjList[j].firstedge;e;e=e->next)
                         {
                                k=e->adjvex;
                                ete = etv[j];
                                lte =ltv[k]-e->weight;
                                if(ete==lte)
                                   printf(“<v%d,v%d>length:%d,”,GL->adjList[j].data,GL->adjList[k].data,e->weight);
                          }
                  }
        }
}
 

 

1. 基本概念

（1）AOV网（Activity On Vertex Network）
AOV网是一个表示工程的有向图中，其中的顶点用来表示活动，弧则用来表示活动之间的优先关系。举个简单的例子，假定起床后可以边煮水，边刷牙洗脸，但洗脸要在刷牙后，煮好水，刷好牙洗好脸以后，就可以喝水了，这个活动的AOV图如下（其中的每个顶点都表示一个活动，而顶点之间的弧表示了活动之间的执行先后顺序）：

（2）AOE网（ Activity On Edge Network）
AOE网是一个表示工程的带权有向图，其中的顶点用来表示某个事件，弧用来表示活动，弧上的权值用来表示活动持续的时间。例如上述例子的AOE网如下：

（3）AOE网和AOV网的区别
AOV网：其顶点用来表示活动。AOE网是用来表示活动之间的制约关系。
AOE网：顶点表示事件，边表示活动，边上的权值用来表示活动持续的时间。AOV网是用来分析工程至少需要花多少时间完成，或是为了缩短时间需要加快哪些活动等问题。

（4）源点、汇点、路径长度
在AOE网中，
始点或源点：入度为0的顶点，它表示一个工程的开始；
终点或汇点：出度为0的顶点，它表示一个工程的结束；
路径长度：路径上各个活动所持续的时间之和。

（5）关键路径、关键活动
在AOE网中，从源点到汇点具有最大长度的路径称为关键路径，在关键路径上的活动称为关键活动。

2. 关键路径算法

2.1 基本思想

（1）要找出一个AOE网中的关键路径，就要先找出网里的关键活动，这些关键活动间的路径就是关键路径。

（2）判断一个活动是不是关键活动，方法是要先找到所有活动的最早开始时间和最晚开始时间，并且对它们进行比较，如果二者相等（意味着这个活动在该工程中没有时间松动），说明这个活动是关键活动。

（3）对于活动<Vi, Vj>，它最早的开始时间等于事件Vi最早的发生时间earlist[Vi]（事件v的最早发生时间用earlist[v]）。假设E[Vi]表示所有到达顶点Vi的弧的集合，len<Vi, Vj>表示活动<Vi, Vj>的持续时间，那么：

注意，这里假设顶点下标从0开始，所以Vi==0，则表示它是源点，因此最早的开始时间为0；当某个顶点不是源点，那么只有在它前面的事件都发生完后，才能轮到这个事件，所以用了max。

（4）对于活动<Vi, Vj>，它最晚的开始时间等于事件Vj最晚的发生时间减去这个活动的持续事件，即latest[Vj]-len<Vi, Vj>（事件v的最晚的发生时间用latest[v])。假设S[Vj]表示所有从顶点Vj出发的弧的集合，len<Vj, Vk>表示活动<Vj, Vk>的持续时间，那么：

2.2 算法实现

（1）数据结构

typedef struct EdgeListNode{ //边表结点
    int adjId;
    int weight;
    EdgeListNode* next;
};

typedef struct VertexListNode{ //顶点表结点
    int in; //入度
    int data;
    EdgeListNode* firstadj; //指向其边表
};

typedef struct GraphAdjList{ //图结构
    int vertexnumber; //顶点个数
    int edgenumber;
    VertexListNode vertextlist[Maximum];
};

（2）具体实现
1）由基本思路可以知道，要求一个AOE网的关键路径，步骤如下：
A. 首先初始化每个顶点的最早开始为0，然后对AOE网进行拓扑排序，在排序的过程中获取每个顶点的最早开始时间；
B. 获取拓扑排序后，初始化每个顶点的最晚开始时间为汇点的最早开始时间，并从AOE网的汇点开始，从后往前，对每个顶点找到求其最晚开始时间；
C. 遍历图中的每条边（方法是遍历图中每个顶点的边表），求其最早开始时间和最晚开始时间，如果二者相等，则这是个关键活动，将其加入关键路径中。

2）代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<sstream>
#include<list>
#include<stdlib.h>
#include<queue>
using namespace std;

#define Maximum 1000

typedef struct EdgeListNode{
    int adjId;
    int weight;
    EdgeListNode* next;
};

typedef struct VertexListNode{
    int in;
    int data;
    EdgeListNode* firstadj;
};

typedef struct GraphAdjList{
    int vertexnumber;
    int edgenumber;
    VertexListNode vertextlist[Maximum];
};

//拓扑排序，返回拓扑排序结果，earlist存储每个顶点的最早开始时间
vector<int> ToplogicalSort(GraphAdjList g, int *earlist) {
    vector<int>v; //存储拓扑排序结果
    queue<int>q; //存储入度为0的顶点
    EdgeListNode *temp;
    int i, j, k, ans;

    ans = 0;
    v.clear();
    while(!q.empty()) {
        q.pop();
    }

	//找出所有入度为0的顶点
    for(i=1; i<=g.vertexnumber; i++) {
        if(g.vertextlist[i].in == 0) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        i = q.front();
        v.push_back(i);
        q.pop();
        ans++;
        temp = g.vertextlist[i].firstadj;
        while(temp != NULL) {
            k = earlist[i] + temp->weight;
            if(k > earlist[temp->adjId]) {
                earlist[temp->adjId] = k;
            }
            j = --g.vertextlist[temp->adjId].in;
            if(j == 0) {
                q.push(temp->adjId);
            }
            temp = temp->next;
        }
    }

    if(ans < g.vertexnumber) {
        v.clear();
    }
    return v;
}

//求关键路径，返回存储关键路径顶点的vector
vector<int> CriticalPath(GraphAdjList g) {
    vector<int>ans;
    vector<int>path;
    int i, j, k, *earlist, *latest;
    EdgeListNode *temp;

	//earlist存储每个顶点的最早开始时间
	//latest存储每个顶点的最晚开始时间
    earlist = (int*)malloc(sizeof(int) * (g.vertexnumber+1));
    latest = (int*)malloc(sizeof(int) * (g.vertexnumber+1));
    path.clear();
    for(i=1; i<=g.vertexnumber; i++) {
        earlist[i] = 0;
    }

    ans = ToplogicalSort(g, earlist);
    for(i=1; i<=g.vertexnumber; i++) {
        latest[i] = earlist[ans[g.vertexnumber-1]];
    }
    for(i=g.vertexnumber; i>0; i--) {
        temp = g.vertextlist[i].firstadj;
        while(temp!=NULL) {
            if(latest[temp->adjId] - temp->weight < latest[i]) {
                latest[i] = latest[temp->adjId] - temp->weight;
            }
            temp = temp->next;
        }
    }

	//遍历每条边
    for(i=1; i<=g.vertexnumber; i++) {
        temp = g.vertextlist[i].firstadj;
        while(temp != NULL) {
            j = earlist[i];
            k = latest[temp->adjId] - temp->weight;
            if(j == k) { //是关键活动
       			//把该活动的两个顶点加入path
                path.push_back(i);
                path.push_back(temp->adjId);
            }
            temp = temp->next;
        }
    }
    return path;
}

（3）测试

int main() {
    GraphAdjList g;
    EdgeListNode *e;
    int i, j, k;

    g.vertexnumber = 5;
    g.edgenumber = 7;


    for(i=1; i<=g.vertexnumber; i++) {
        g.vertextlist[i].data = i;
        g.vertextlist[i].firstadj = NULL;
    }

    g.vertextlist[1].in = 0;
    g.vertextlist[2].in = 1;
    g.vertextlist[3].in = 2;
    g.vertextlist[4].in = 2;
    g.vertextlist[5].in = 1;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 2; e->weight = 2; e->next = g.vertextlist[1].firstadj; g.vertextlist[1].firstadj = e;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 4; e->weight = 1; e->next = g.vertextlist[1].firstadj; g.vertextlist[1].firstadj = e;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 5; e->weight = 1; e->next = g.vertextlist[1].firstadj; g.vertextlist[1].firstadj = e;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 3; e->weight = 3; e->next = g.vertextlist[2].firstadj; g.vertextlist[2].firstadj = e;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 4; e->weight = 5; e->next = g.vertextlist[2].firstadj; g.vertextlist[2].firstadj = e;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 3; e->weight = 8; e->next = g.vertextlist[4].firstadj; g.vertextlist[4].firstadj = e;

    e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
    e->adjId = 3; e->weight = 1; e->next = g.vertextlist[5].firstadj; g.vertextlist[5].firstadj = e;

    vector<int>ans;
    ans = CriticalPath(g);

    for(i=0; i<ans.size(); i+=2) {
        cout<<ans[i]<<"->"<<ans[i+1]<<endl;
    }
    cout<<endl;

    return 0;
}