-
2021-05-16 10:01:48
相关概念
AOE网
AOE网(Activity On Edge Network)用边表示活动,用顶点表示事件(活动的完成)。边是带权的,表示活动需要的时间。
源点与汇点
源点:入度为0的点,表示一个工程的开始。
汇点:出度为0的点,表示一个工程的结束。
关键活动与关键路径
在AOE网中,从源点到汇点最长的路径称为关键路径,在关键路径上的活动称为关键活动。
因为AOE网中的活动是可以并行进行的,所以整个工程的时间开销,其实是最长路径的时间开销。即关键路径制约整个工程的工期。
>_< 看个图理解一下上面的定义吧!!!
加深理解
通过AOV网与AOE网的比较,我们更能够深刻的理解二者。
相同点
都是有向无环图(DAG);都存在拓扑限制。
不同点
AOV网的顶点表示活动,边无权。AOV网用来分析活动之间的制约关系。
AOE网的顶点表示事件(活动的完成),边表示活动,权值为活动的持续时间。AOE网用来分析工程的最小时间限制,也就是说,缩短哪些活动持续时间可以缩短整个工程的工期(关键活动),缩短哪些活动持续时间并没有意义(非关键活动)。
关键路径算法(理论)
在说关键路径算法之前,你需要弄懂下面的几个重要参量及其求法:
事件 vk 的最早发生时间 ve(k) —— 它是从源点v1到某个顶点vk的最长路径长度。它决定了之后的活动能够开工的最早时间。
ve(源点) = 0
ve(k) = max{ve(j) + cost(j, k)}
事件 vk 的最迟发生时间 vl(k) —— 它是指在不推迟整个工期的前提下,该事件最迟必须发生的事件。
vl(汇点) = ve(汇点)
vl(k) = min{vl(j) - cost(k, j)}
活动 ai 的最早开始时间 e(i) —— 它是该活动的起点表示的事件的最早发生时间。
活动为(k, j),则 e(i) = ve(k)
活动 ai 的最迟开始时间 l(i) —— 它是该活动的终点表示的事件的最迟发生事件该活动所需时间之差。
活动为(k, j),则 l(i) = vl(j) - cost(k, j)
好了,下面正式介绍关键路径算法。
1)从源点出发,令 ve(源点) = 0,按拓扑顺序求出所有顶点(事件)的最早发生时间 ve()
2)从汇点出发,令 vl(汇点) = ve(汇点),按拓扑逆序求出所有顶点(事件)的最迟发生时间 vl()
3)根据各顶点的 ve() 值求出所有边(活动)的最早开始时间 e()
4)根据各顶点的 vl() 值求出所有边(活动)的最迟开始时间 l()
5)e() = l() 的边构成关键路径;关键路径上的顶点为关键活动。
关键路径算法(举例)
题目如图:
具体流程:
ve(1) = 0
ve(2) = ve(1) + 3 = 3
ve(3) = ve(1) + 2 = 2
ve(4) = max{ve(2) + 2, ve(3) + 4} = max{5, 6} = 6
ve(5) = ve(2) + 3 = 6
ve(6) = max{ve(5) + 1, ve(4) + 2, ve(3) + 3} = max{7, 8, 5} = 8vl(6) = ve(6) = 8
vl(5) = vl(6) - 1 = 7
vl(4) = vl(6) - 2 = 6
vl(3) = min{vl(4) - 4, vl(6) - 3} = min{2, 5} = 2
vl(2) = min{vl(5) - 3, vl(4) - 2} = min{4, 4} = 4
vl(1) = min{vl(2) - 3, vl(3) - 2} = min{1, 1, } = 1e(1) = ve(1) = 0
e(2) = ve(1) = 0
e(3) = ve(2) = 3
e(4) = ve(3) = 3
e(5) = ve(3) = 2
e(6) = ve(3) = 2
e(7) = ve(4) = 6
e(8) = ve(5) = 6l(1) = vl(2) - 3 = 1
l(2) = vl(3) - 2 = 0
l(3) = vl(4) - 2 = 4
l(4) = vl(5) - 3 = 4
l(5) = vl(4) - 4 = 2
l(6) = vl(6) - 3 = 5
l(7) = vl(6) - 2 = 6
l(8) = vl(6) - 1 = 7e(2) == l(2)
e(5) == l(5)
e(7) == l(7)最终结果:
补充说明
① 关键路径上的活动是关键活动,它是决定整个工程工期的关键因素,即通过加快关键活动来缩短整个工程的工期。但是注意关键活动的缩短存在一个下限,因为一旦缩短到一定的程度,这条路径就不再是关键路径,该关键活动就会变成非关键活动。
② AOE网的关键路径并不唯一,即关键路径可能有多条。且对于有几条关键路径的网,只提高一条关键路径上的关键活动并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
☘️
更多相关内容 -
关键路径
2018-03-10 13:05:56AOE网 无环赋权有向图:顶点表示事件,弧表示活动 ...关键路径(不一定唯一,但长度相等):源点到终点的最长路径 关键活动:关键路径上的活动 事件vj的最早发生时间ve(j)、事件vi的最迟发生时间vl(i) vAOE网 无环赋权有向图:顶点表示事件,弧表示活动
关键活动按时开始和完成,不会影响整个工程的进度。
只有缩短关键活动的完成时间才有可能缩短整个工程完成时间。
非关键活动,即使缩短完成时长也不一定能缩短整个工程完成时间。
关键路径(不一定唯一,但长度相等):源点到终点的最长路径
关键活动:关键路径上的活动
事件vj的最早发生时间ve(j)、事件vi的最迟发生时间vl(i)
ve(j):从源点v0到vj的最长路径的长度。
vj一旦发生,以vj为起点的各条出边<vj,vk>所表示活动aj可以开始,即ve(j)=ae(j)
vl(i):从终点vn-1开始计算。vl(n-1)=ve(n-1)。vl(i)为其(后继事件的最迟发生时间减去各个vi到vj路径上的活动时长)的最小值
该图中vl(1)=6,表格中有错应做修改
活动<i,j>的最早开始时间ae(<i,j>)、最迟开始时间al(<i,j>)
活动<i,j>的最早开始时间=事件vi的最早发生时间
活动<i,j>的最迟开始时间=事件vj的最迟发生时间-活动<i,j>的时长
该图中,活动名称a1...a11应改为a0...a10
ae(<i,j>)=al(<i,j>)的活动为关键活动。
-
关键路径详解
2019-11-22 15:46:36AOV网: 顶点活动(Activity On Vertex,AOV)网是指用顶点表示活动,而用边集表示活动间优先关系的有...显然,图中不应当存在有向环,否则会让优先关系出现逻辑错误。 AOE网: 边活动(Activity On Edge,A...AOV网:
顶点活动(Activity On Vertex,AOV)网是指用顶点表示活动,而用边集表示活动间优先关系的有向图。例如图10-57的先导课程示意图就是AOV网,其中图的顶点表示各项课程,也就是“活动”;有向边表示课程的先导关系,也就是“活动间的优先关系”。显然,图中不应当存在有向环,否则会让优先关系出现逻辑错误。
AOE网:
边活动(Activity On Edge,AOE)网是指用带权的边集表示活动,而用顶点表示事件的有向图,其中边权表示完成活动需要的时间。例如图10-59中,边a1~a6表示需要学习的课程,也就是“活动”,边权表示课程学习需要消耗的时间;顶点V1~V6。表示到此刻为止前面的课程已经学完,后面的课程可以开始学习,也就是“事件”(如V5表示a4计算方法和a3实变函数已经学完,a6泛函分析可以开始学习。从另一个角度来看,a6只有当a4和a5都完成时才能开始进行,因此当a4计算方法学习完毕后必须等待a5实变函数学习完成后才能进入到a6泛函分析的学习),显然“事件”仅代表一个中介状态。
源点:在AOE网中,没有入边的顶点称为源点;如顶点V1
终点:在AOE网中,没有出边的顶点称为终点;如顶点V6
AOE网的性质:
·只有在进入某顶点的活动都已经结束,该顶点所代表的事件才发生;
·只有在某顶点所代表的事件发生后,从该顶点出发的各活动才开始;
AOE网中的最长路径被称为关键路径(强调:关键路径就是AOE网的最长路径),而把关键路径上的活动称为关键活动,显然关键活动会影响整个工程的进度。
关键概念:
1.事件的最早发生时间ve[k](earliest time of vertex):即顶点vk的最早发生时间。
从源点向终点方向计算
ve[0] = 0
ve[1] = ve[0] + a0 = 0 + 4 = 4
ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6
ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10
2.事件的最晚发生时间vl[k](latest time of vertex):即顶点vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。
从终点向源点方向计算
vl[3] = ve[3] = 10
vl[2] = vl[3] - a3 = 10 - 4 = 6
vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4//之所以求最小,保证其他的点的最晚发生时间
vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0
3.活动的最早开工时间e[k](earliest time of edge):即弧ax的最早发生时间。
5条边,5个活动
e[0] = ve[0] = 0
e[1] = ve[0] = 0
e[2] = ve[1] = 4
e[3] = ve[2] = 6
e[4] = ve[1] = 4
4.活动的最晚开工时间l[k](latest time of edge):即弧ak的最晚发生时间,也就是不推迟工期的最晚开工时间。
e[0] = v[1] - a0 = 4 - 4 = 0
e[1] = vl[2] - a1 = 6 - 3 = 3
e[2] = vl[2] - a2 = 6 - 2 = 4
e[3] = vl[3] - a3 = 10 - 4 = 6
e[4] = vl[3] - a4 = 10 - 6 = 4
活动的最早开始时间和最晚开始时间相等,则说明该活动时属于关键路径上的活动,即关键活动
算法设计:
关键路径算法是一种典型的动态规划法,设图G=(V, E)是个AOE网,结点编号为1,2,...,n,其中结点1与n 分别为始点和终点,ak=<i, j>∈E是G的一个活动。算法关键是确定活动的最早发生时间ve[k]和最晚发生时间vl[k],进而获取顶点的最早开始时间e[k]和最晚开始时间l[k]。
根据前面给出的定义,可推出活动的最早及最晚发生时间的计算方法:
e(k) = ve(i)
l(k) = vl(j) - len(i,j)
结点的最早发生时间的计算,需按拓扑次序递推:
ve(1) = 0
ve(j) = MAX{ etv(i)+len(i, j) }
对所有<i,j> ∈E的i 结点的最晚发生时间的计算,需按逆拓扑次序递推:
vl(n) = ve(n)
vl(i) = MIN{vl(j) - len(i, j)} 对所有<i,j>∈E的j
这种计算方法, 依赖于拓扑排序, 即计算ve( j) 前,应已求得j 的各前趋结点的ve值,而计算vl(i)前,应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行,即在每输出一个结点i后,在删除i的每个出边<i,j>(即入度减1)的同时,执行
if ( ve[i]+len(i,j)) > ve[j] )
ve[j] = ve[i] + len(i,j)
这时会发现,如果想要获得ve[j]的正确值,ve[il]~ve[ik]必须已经得到。有什么办法能够在访问某个结点时保证它的前驱结点都已经访问完毕呢?没错,使用拓扑排序就可以办到。
当按照拓扑序列计算ve数组时,总是能保证计算ve[i]的时候ve[il]~ve[ik]都已经得到。但是这时又碰到另一个问题,通过前驱结点去寻找所有后继结点很容易,但是通过后继结点V;去寻找它的前驱结点V1~Vx似乎没有那么直观。一个比较好的办法是,在拓扑排序访问到某个结点时,不是让它去找前驱结点来更新ve[i],而是使用ve[i]去更新其所有后继结点的ve值。通过这个方法,可以让拓扑排序访问到V;的时候,V1~Vk一定都已经用来更新过ve[i],此时的ve[i]便是正确值,就可以用它去更新V;的所有后继结点的ve值。
//拓扑序列 stack<int>topOrder; //拓扑排序,顺便求ve数组 bool topologicalSort() { queue<int>q; for(int i=0;i<n;i++) if(inDegree[i]==0) q.push(i); while(!q.empty()) { int u=q.front(); q.pop(); topOrder.push(u);//将u加入拓扑序列 for(int i=0;i<G[u].size();i++) { int v=G[u][i].v;//u的i号后继结点编号为v inDegree[v]--; if(inpegree[v]==0) q.push(v); //用ve[u]来更新u的所有后继结点 if(ve[u]+G[u][i].w> ve[v]) ve[v]=ve[u]+G[u][i].w; } } if(toporder.size()== n) return true; else return false; }
同理,如图10-64所示,从事件V出发通过相应的活动ar1~ark可以到达k个事件V1~Vk,活动的边权为length[r1]~length[rk]。假设已经算好了事件V1~Vk的最迟发生时间xl[j1]~vl[jk],那么事件Vi的最迟发生时间就是vl[j1]-length[r1]~vl[jk]-length[rk]中的最小值。此处取最小值是因为必须保证Vj1~Vjk的最迟发生时间能被满足;可以通过下面这个公式辅助理解。
和ve数组类似,如果需要算出vl[i]的正确值,vl[j1]~vl[jk]必须已经得到。这个要求与ve数组的刚好相反,也就是需要在访问某个结点时保证它的后继结点都已经访问完毕,而这可以通过使用逆拓扑序列来实现。幸运的是,不必再做一次逆拓扑排序来得到逆拓扑序列,而是可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。此时会发现,在上面实现拓扑排序的过程中使用了栈来存储拓扑序列,那么只需要按顺序出栈就是逆拓扑序列。而当访问逆拓扑序列中的每个事件Vi时,就可以遍历Vi的所有后继结点Vj1~Vjk,使用vI[j1]~vl[jk]来求出vl[i]。
这部分的代码如下所示:
fill(vl,v1+n,ve[n-1]);//v1数组初始化,初始值为终点的ve值 //直接使用toporder出栈即为逆拓扑序列,求解v1数组 while(!topOrder.empty()) { int u=topOrder.top();//栈顶元素为u topOrder.pop(); for(int i=0;i<G[u].size();i++) { int v=G[u][i].v;//u的后继结点v //用u的所有后继结点v的v1值来更新v1[u] if(vl[v]-G[u][i].w < vl[u]) vl[u]=vl[v]-G[u][i].w; } }
通过上面的步骤已经把求解关键活动的过程倒着推导了一遍,下面给出上面过程的步骤总结,即“先求点,再夹边”:
①按拓扑序和逆拓扑序分别计算各顶点(事件)的最早发生时间和最迟发生时间:
②用上面的结果计算各边(活动)的最早开始时间和最迟开始时间:
③e[i-→] = l[i-→i]的活动即为关键活动。
主体部分代码如下(适用汇点确定且唯一的情况,以n-1号顶点为汇点为例):【主体代码】
求取关键路径:
//遍历邻接表的所有边,计算活动的最早开始时间e和最迟开始时间1 for(int u=0;u<n;u++) { for(int i=0;i<G[u].size();i++) { int v=G[u][i].v,w=G[u][i].w; //活动的最早开始时间e和最迟开始时间1 int e=ve[u],l=vl[v]-w; //如果e==1,说明活动u->v是关键活动 if(e==1) printf("%d->%d\n",u,v);//输出关键活动} } return ve[n-1];//返回关键路径长度 }
在上述代码中,没有将活动的最早开始时间e和最迟开始时间l存储下来,这是因为一般来说e和l只是用来判断当前活动是否是关键活动,没有必要单独存下来。如果确实想要将它存储下来,只需要在结构体Node中添加域e和1即可。
如果事先不知道汇点编号,有没有办法比较快地获得关键路径长度呢?当然是有办法的,那就是取ve数组的最大值。原因在于,ve数组的含义是事件的最早开始时间,因此所有事件中ve最大的一定是最后一个(或多个)事件,也就是汇点。于是只需要在fill函数之前添加一小段语句,然后改变下vl函数初始值即可,代码如下:
int maxLength = 0; for(int i=0; i<n; ++i) { if(ve[i] > maxLength) maxLength = ve[i]; } fill(vl, vl + n, maxLength);
-
拓扑排序以及求解关键路径
2019-10-29 17:14:33拓扑排序以及求解关键路径都是属于有向无环网的应用 拓扑排序:解决工程能否顺序进行的问题 介绍2个概念 AOV网:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示...拓扑排序以及求解关键路径都是属于有向无环网的应用
拓扑排序:解决工程能否顺序进行的问题
介绍2个概念
AOV网:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网。
- 弧表示活动之间的某种制约关系:比如演职人员确定了,场地联系好了,才可以开始进场拍摄。
- AOV网中不能存在回路,即不能存在环,否则某个活动的开始要以自己完成作为先决条件,这是不现实的
拓扑序列:
设G=(V,E)是一个具有n个顶点的有向图,
中的顶点序列
~
,满足若从顶点
到
有一条路径,则在顶点序列中顶点
必定在
之前,则我们称这样的顶点序列为一个拓扑序列
拓扑排序:对一个有向图构造拓扑序列的过程。
如果此网的全部顶点都被输出,则说明它是不存在环或回路的AOV网;
如果输出的顶点数少于总共的顶点数,则说明这个网存在环或回路,不是AOV网;
拓扑排序算法:
基本思路:
从AOV网中选择一个入度为0的顶点输出,然后删除此顶点,并且删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或AVO中不存在入度为0的顶点为止。
确定使用的数据结构:由于需要删除顶点和边,所以用邻接表比较方便
typedef struct EdgeNode { int adjvex; int weight; struct EdgeNode *node; }EdgeNode;//边结点(带有权值) typedef struct VertexNode { int in;//该顶点入度 int data;//顶点域 EdgeNode *firstedge;//边表头指针 }VertexNode,AdjList[MAXVEX];//顶点表结点 typedef struct { AdjList adjList; int numVertexes,numEdges;//当前图的顶点数和边数 }graphAdjList,*GraphAdjList;
看代码:
//这里使用栈存储入度为0的顶点,避免每个查找都要遍历顶点表找有没有入度为0的顶点 Status TopologicalSort(GraphAdjList G) { EdgeNode *e; int count=0;//统计输出顶点个数 int top=0;//栈指针下标 int *stack; stack=(int*)malloc(G->numVertexes*sizeof(int)); for(int i=0;i<G->numVertexes;i++) if(G->adjList[i].in==0) stack[++top]=i;//将入度为0的顶点入栈 while(top!=0)//top!=0说明栈非空,存在入度为0的顶点 { int gettop=stack[top--]; print("%d --> ",G->adjList[gettop].data); count++;//统计输出顶点数 for(e=G->adjList[gettop].firstedge;e;e=e->next) {//删除以顶点k为尾的弧,并将弧头顶点的入度-1 int k=e->adjvex; if(!(--G->adjList[k].in)//先自减,然后判断减完是否等于0 stack[++top]=k;//变成入度为0的顶点需要入栈 } } if(count<G->numVertexes) return ERROR;//存在环,无法得到拓扑序列 else return OK; }
- 拓扑排序得到的拓扑序列不唯一
- 对于n个顶点和e条边的AOV网,算法时间复杂度为O(n+e)
关键路径:解决工程完成需要的最短时间问题
拓扑排序:解决工程能否顺序进行的问题
求解关键路径:解决工程完成需要的最短时间问题
解决工程完成需要最短时间问题前提是工程一定能顺利进行和完成,故拓扑排序是求解关键路径的基础。不存在拓扑序列的有向图无法求解关键路径,求解关键路径之前需进行拓扑排序。
新概念:AOE网
在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE(Activity on Edge Network)。正常情况下AOE有一个源点一个汇点
始点/源点:有向图中没有入边的顶点,表示一个工程的开始 终点/汇点:有向图中没有出边的顶点,表示一个工程的结束
如下图所示:
特别强调:
- 某个顶点代表的事件发生后,从该顶点出发的各活动可以立马开始
- 只有在进入某顶点的各活动都已经结束,该顶点代表的事件才能发生
后面的最早最晚时间点根据此处理解,比如事件的最早发生时间,最晚发生时间等等
再介绍几个概念:
路径长度:路径上各个活动所持续时间之和称为路径长度
关键路径:从源点到汇点具有最大长度的路径叫关键路径
关键活动:关键路径上的活动叫关键活动
我们的目标:解决工程完成需要的最短时间问题,尽可能缩短工程完成的耗时。
缩短工期长度:只有缩短关键路径上关键活动的时间才能减少整个工期长度
所以,我们需要找到关键路径,缩短关键路径上关键活动的时间,以减少整个工程完成的时间
关键活动:活动的最早开始时间和最晚开始时间相等的话就是意味着此活动是关键活动,活动间的路径为关键路径,否则不是
定义几个参数:
- etv(earliest time of vertex):顶点事件最早发生的时间点
- ltv(latest time of vertex):顶点事件最晚发生的时间点,最晚需要开始的时间,超过此时间将会延误工期
- ete(earliest time of edge):活动最早发生的时间点
- lte(latest time of edge):活动最晚发生的时间点,不推迟工期的最晚开工时间
我们由1和2来求得3和4,然后根据相对应的活动的ete和lte是否相等判断是否是关键活动
先求etv,求etv的过程,就是从头到尾找拓扑序列的过程。
因此在求关键路径之前需调用一次拓扑排序算法计算etv和存储得到的拓扑序列。
int *etv,*ltv;//事件发生的最早时间和最迟发生时间数组 int *stack2;//存储拓扑序列 int top2;//stack2的栈顶指针
改进过的拓扑排序算法:
不再打印拓扑序列而是存储拓扑序列到Stack2,我们能得到一个拓扑序列,因此能确定工程的源点和终点
Status TopologicalSort(GraphAdjList G) { EdgeNode *e; int count=0;//统计输出顶点个数 int top=0;//栈指针下标 int *stack; stack=(int*)malloc(G->numVertexes*sizeof(int)); for(int i=0;i<G->numVertexes;i++) if(G->adjList[i].in==0) stack[++top]=i;//将入度为0的顶点入栈 etv=(int*)malloc(G->numVertexes*sizeof(int)); for(int i=0;i<G->numVertexes;i++) etv[i]=0;//初始化为0 int top2=0;//栈顶指针 stack2=(int*)malloc(G->numVertexes*sizeof(int)); while(top!=0) { int gettop=stack[top--];//去stack中入度为0的顶点 count++;//统计顶点个数,用于最后判断有向图是否有环 stack2[++top2]=gettop;//将从stack中出来的入度为0的顶点入stack2,stack2中存放拓扑序列 for(e=G->adjList[gettop].firstedge;e;e=e->next) { int k=e->adjvex; if(!(--G->adjList[k].in)//先自减,然后判断减完是否等于0 stack[++top]=k;//变成入度为0的顶点需要入栈 if((etv[gettop]+e->weight)>etv[k])//求各顶点事件最早发生时间 etv[k]=etv[gettop]+e->weight; } } if(count<G->numVertexes) return ERROR;//出错,有环 else return OK;//存在拓扑序列,并存在Stack2中 }
如何理解:
- 当顶点k为源点时,时间最早开始时间等于0;
- 当顶点k不是源点时,已知该顶点的前驱顶点的最早开始时间,只有进入该顶点的各活动已经结束,该顶点代表的事件才能发生。即该顶点k最早发生时间=max(顶点i事件最早发生的时间点+顶点之间活动的耗时)。举个例子:一个老师最早在下午2点的时候就布置了作业,已知小明大概要做2个小时,小李要做1个半小时,小红要做50分钟,现在问老师最早什么时候能收齐作业。答案不言而喻,需要等小明做完才能收齐作业本吧!应该最早4点才能收齐,3点收作业小明做不完的呀!
- 如下图:
接下来看关键路径算法:
void CriticalPath(GraphAdjList G) { EdgeNode *e; int ete,lte;//相应活动的最早发生时间和最迟发生时间变量 TopologicalSort(G);//先进行拓扑排序 int ltv=(int*)malloc(G->numVertexes*sizeof(int));//事件最晚发生的时间 for(int i=0;i<G->numVertexes;i++)//对ltv初始化 ltv[i]=etv[G->numVertexes-1];//为啥初始化成etv[G->numVertexes-1]? //因为根据之前得到拓扑排序得到终点的最早的发生时间,终点事件的最早发生时间等于最晚发生时间 //为啥呢?既然都到终点了,还分早晚?这个终点的最早发生时间意味着无论如何前面的活动都已经完成 //此刻已经无需等待,最晚时间没有意义,它之前顶点的最晚时间必须小于终点的最晚发生时间 while(top2!=0)//拓扑序列的逆序,我们需要从终点倒推出每个事件的最晚发生时间 { int gettop=stack2[top2--];//拓扑序列倒序出栈 for(e=G->adjList[gettop].firstedge;e;e=e->next) { int k=e->adjvex;//k是gettop的领接顶点,有弧<gettop,k> if(ltv[k]-e->weight<ltv[gettop])//已知顶点k的最晚发生时间 ltv[gettop]=ltv[k]-e->weight;//求gettop顶点的最晚发生时间 }//已知某顶点后序领接顶点事件的最晚发生时间,求该顶点最晚发生时间。见正文分析 } for(int j=0;j<G->numVertexes;j++) { //对每一条弧表示的活动,求活动的最早开始时间,和活动最晚发生时间 for(e=G->adjList[gettop].firstedge;e;e=e->next) { int k=e->adjvex;//k是顶点j的后序领接顶点,即存在弧<j,k>表示一个活动 ete=etv[j];//活动的最早开始时间就等于顶点j表示事件的最早发生时间, lte=ltv[k]-e->weight;//活动的最晚发生时间就等于顶点k最晚发生时间减活动所需时间 if(ete==lte){ //两者相等则此活动没有任何空闲,其在关键路径上,且为关键活动 printf("<V%d,V%d> length:%d,",//打印输出关键路径 G->adjList[j].data,G->adjList[k].data,e->weight); } } } }
如何理解以上式子:
- 当k=n-1时,表示顶点k是终点。终点的最晚发生时间和最早发生时间是相等的。至于为什么!既然都到终点了,还分早晚?这个终点的最早发生时间意味着无论如何前面的活动都已经完成,此刻已经无需等待,最晚时间没有意义。工程应尽快完成为好。
- 当k!=n-1时,表示顶点k不是终点,且已知顶点j,并且存在活动<k,j>。顶点k最晚发生时间=Min(顶点j最晚发生时间-活动<k,j>活动耗费时间)。举个例子:假设老师打算布置一次作业,老师最晚下午4点要收上去批改作业,现在已知小明大概要做2个小时,小李要做1个半小时,小红要做50分钟,现在好了,为了到时候最晚4点能都收好所以作业,老师应该最晚几点把题目给大家布置出来。当然是最晚2点!如果是3点布置作业会有同学无法完成,所以最晚2点布置,当然1点布置也可以让大家完成。
见下图:
对于活动的最早发生时间ete和最晚发生时间lte:
总结:
- 算法的时间复杂度为O(n+e)
- AOE网可能存在多条关键路径,单独提高一条关键路径上的关键活动速度并不能导致整个工程缩短工期,需同时提高几条关键路径上活动的速度。
参考资料:大话数据结构
-
为什么事件的最早发生时间是源点到顶点的最长路径长度?(关键路径详解)
2020-11-30 20:20:04在学习数据结构的过程中,我发现关键路径的中的概念取名使得第一印象让人容易产生误解,所以我用最通俗易懂的例子来解释解释这些概念的实际含义。 基本概念——AOE网 有几个最基本的概念我们要先了解,在带权有向图... -
数据结构之——关键路径
2020-06-06 23:07:57(2)网中的关键路径并不唯一。且对于有几条关键路径的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能到达缩短工期的目的。 -
拓扑排序和关键路径算法----关键路径算法 (C语言实现)
2020-07-22 12:15:26关键路径的特征是:从起点 (起点是唯一的,入度为0) 到终点 (终点是唯一的,出度为0) 的一个有向图中,该路径上的弧 (有向图的边称之为“弧”) 的权重的和最大。关键路径可能不是唯一的,但不同的关键路径上的权重之... -
Python小白的数学建模课-21.关键路径法
2021-07-15 10:52:35NetworkX 提供了拓扑序列和关键路径的函数,但没有给出计划网络分析的时间参数,如事件的最早开工时间、最晚结束时间,因此不能实现对计划网络图的分析和优化。 本文的案例给出了关键路径算法的完整例程,并同时计算... -
关键路径,前导图,箭线图
2020-12-21 09:49:58关键路径,通常是决定项目工期的活动序列。它是项目中最长的路径,即使变动很小也会影响项目工期。项目活动图,包括前导图和箭线图前导图(也叫单代号网络图,顺序图):节点表示活动,箭线表示逻辑箭线图(也叫双代号... -
数据结构算法之关键路径
2020-07-14 18:41:23关键路径 文章目录: 基本概念 关键路径的构造过程 关键路径的特点 1.基本概念 首先要了解AOE网和关键路径的基本概念 这里详细说明一下,AOE网和AOV网的区别和联系: 联系:都代表的是有向无环图。 区别: 1.AOE... -
关键路径(AOE网)
2014-10-15 14:35:46如果该活动没有空余时间,也就是最早活动时间和最晚活动时间相等, 那么你该活动就是关键活动,关键活动组成的一条路径称之为关键路径,关键路径可能不唯一,这取决于图的形态。 与关键路径有关的几个概念: ... -
关键路径法详解【CPM】
2018-09-01 22:26:33CPM(CriticalPathMethod 关键路径法)是项目管理中最基本也是非常关键的一个概念,它上连着WBS(工作分解结构),下连着执行进度控制与监督。关键路径是项目计划中最长的路线。 它决定了项目的总实耗时间。项目经理... -
图(五)——AOV网的拓扑排序与AOE网的关键路径
2019-07-23 13:46:35本文第一部分介绍了不带权值的AOV网,以及求AOV网络的拓扑排序的算法和步骤,AOV网络通过拓扑排序判断是否存在回路;本文第二部分介绍了带权值的AOE网,以及求AOE网络的关键路径的算法和步骤。 -
5.4.4 关键路径
2016-09-18 15:41:27在带权有向图中,以顶点表示时间,有向边表示活动,边上的权值表示完成该活动的开销(如完成活动所需的时间),则称这种有向图为用边表示活动的网络,简称为AOE网。 ①只有在某顶点所代表的时间发生或,从该顶点... -
关键路径--经典算法
2017-11-28 21:36:10在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如: 图1 图1 是一个网。其中有9个事件v1,v2,…,v9;11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如 -
【数据结构与算法基础】AOE网络与关键路径
2020-12-06 22:38:06数据结构,一门数据处理的艺术,精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美,在为信息技术打下坚实地基的同时,也令无数开发者和探索者为之着迷。 也因如此,它作为博主大二上学期最重要的... -
图的应用-拓扑排序及关键路径求解
2020-05-14 15:19:33关键路径2.1 关键路径概述2.2 关键路径算法2.2.1 事件最早发生时间etv计算2.2.2 事件最晚发生时间ltv及关键路径计算 1. 拓扑排序 1.1 拓扑排序简介 有⼀个表示⼯程的有向图中, ⽤顶点表示活动, 用弧表示活动之间的... -
有向无环图—关键路径详解(最通俗易懂的版本)【数据结构】
2021-01-10 15:00:50文章目录有向无环图拓扑排序AOV-网AOE-网关键路径的概念事件的最早/晚开始时间事件和活动的区分活动的最早/晚开始时间 有向无环图 拓扑排序 AOV-网 由于有向无环图可以用一种自然的方式对优先关系或依赖关系进行... -
关键路径法
2014-05-02 11:49:19关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种,属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-... -
【数据结构】有向无环图(AOE-网)的关键路径(C语言)
2022-02-21 12:21:30把用顶点表示事件,用弧表示活动,弧的权值表示活动所需要的时间的有向无环图称为边表示活动的网,...从源点到汇点的最长路径长度即为完成整个工程任务所需的时间,该路径称为关键路径。关键路径上的活动称为关键活动。 -
利用AOE网求解关键路径问题
2017-05-08 19:20:37利用AOE网求解关键路径问题,输出一个工程的所有关键活动。 -
求关键路径
2015-03-30 10:37:52求关键路径 1、重要概念 (1)AOE (Activity On Edges)网络 如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(Activity),用边上的权值表示活动的持续时间(Duration),用顶点表示事件... -
redis——为什么选择了跳表而不是红黑树?
2019-10-14 20:32:33跳表是个啥东西请看这...在分析之前,我们还需要着重指出的是,执行插入操作时计算随机数的过程,是一个很关键的过程,它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数,它的计算... -
14. 计算工程完成的关键路径
2017-12-01 23:02:14说明: AOE 网络是有向无环加权图,其中顶点...如果排序结果不唯一,请输出按照从小到大的顺序排列的结果。从小到大的顺序就是输入的节点序列顺序(参见下面关于输入格式的说明)。如图1中满足要求的拓扑排序是: ... -
关键路径法详解
2010-06-08 19:05:00关键路径法)是项目管理中最基本也是非常关键的一个概念,它上连着WBS(工作分解结构),下连着执行进度控制与监督。关键路径是项目计划中最长的路线。 它决定了项目的总实耗时间。项目经理必须把注意力集中于那些... -
为什么OceanBase不适合银行的三点思考
2020-02-13 16:21:47需要强调的是,尽管两种不同的技术路径,但技术原理却是相同的。分布式和集中式数据库各有优缺点,也就各有不同的适用环境。 2002年,麻省理工学院MIT的教授在数学上证明了CAP理论。在分布式计... -
48. 数据结构笔记之四十八的有向无环图的应用关键路径
2017-09-21 21:29:0448. 数据结构笔记之四十八的有向无环图的应用关键路径 “富贵不淫贫贱乐 , 男儿到此是豪雄。-- 程颢” 来看下有向无环图的另一个应用关键路径。 1. 关键路径 与AOV-网相对应的是AOE-网(Activity On Edge)即边表示... -
为Python文件访问选择路径
2021-02-11 05:11:23当然,您不想直接将文件放在home中,但是其中的一个子目录(如果还没有的话,您必须创建它)是一个合理的默认值。在当然,请允许此设置被传递给程序的环境变量或命令行标志覆盖,因为某些平台对于应用程序按惯例应存放... -
拓扑排序之关键路径(深度优先搜索)
2014-11-18 22:04:15采用深度优先搜索进行拓扑排序,获取拓扑序列的同时计算各顶点事件的最早发生时间,然后逆序计算各顶点事件...本文是《大话数据结构》的读书笔记,在输出关键路径时采用深度优先搜索输出关键路径,能输出多条关键路径。 -
最小生成树_AOV网(拓扑排序)_AOE网(关键路径)_最短路径
2013-12-07 20:54:50以保证该路径的唯一.重点就在于权值的最小. 算法 普里姆算法: 该算法利用两个集合,一个是保存了,已经找到的符合条件(权值最小)的弧的顶点集合U,一个是保存了除U集合剩下的顶点的集合S. 若图G = {顶点V, 弧E}, 那么S...