本文共 9083 字,大约阅读时间需要 30 分钟。
关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。
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和拓扑序列列表。为此我们首先在程序开始处声明几个全局变量。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)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网中,从源点到汇点具有最大长度的路径称为关键路径,在关键路径上的活动称为关键活动。(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>的持续时间,那么:
(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#include #include #include
(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 ans; ans = CriticalPath(g); for(i=0; i"< <