精华内容
下载资源
问答
  • 图的关键路径,是拓扑序列的一条,可用理解为用来计算最优,或最差拓扑序列,用来预估走完整个图的拓扑序列,需要的时间最多时间。 概念 AOE网:一个带权的有向图中,顶点表示事件,边表示活动,权值表示活动...

    全知识整理目录

    数据结构整理的目录包括了许多的数据结构相关知识。


    目录

    概述

    概念 

    具体实例


    概述

    图的关键路径是什么,有什么用?

    图的关键路径,是拓扑序列的一条,可用理解为用来计算最优,或最差拓扑序列,用来预估走完整个图的拓扑序列,需要的最短时间最多时间。

    概念 

    AOE网:一个带权的有向图中,顶点表示事件,边表示活动,权值表示活动持续的时间,称这样的图为AOE网。

    源点:在AOE网中,没有入边的顶点称为源点。

    终点:在AOE网中,没有出边的顶点称为终点。

    AOE网的性质

    1.         只有在进入事件的活动都已经结束,才表示该顶点所代表的事件发生了。
    2.         只有该事件发生后,该事件的后续活动才开始进行。

    实例1

    事件最早发生时间:

    从源点开始向终点方向计算

    ve[0]=0

    ve[1]=ve[0]+a0=4

    v[2]=max(ve[0]+a1,ve[1]+a2)=6

    ve[3]=max[ve[1]+a4,ve[2]+a3]=10

    ps:最早发生时间,就是边上最大权值的。

    事件最迟发生时间:

    从终点开始,从源点方向计算

    vl[3]=ve[3]=10

    vi[2]=vi[3]-a3=6

    vl[1]=min(vl[3] - a4,vl[2]-a2)=4

    vl[0]=min(vl[2] - a1,vl[1]-a0)=0

    ps:最迟发生时间就是,从终点开始,每次选出活动时间最短的一条边。

    总之记住一句话e(i)=从原顶点开始,最长持续时间的活动,l(i)=从终点开始,最短持续时间活动。

    上图可用得到如下表。(注意是到活动,不是事件)

    a0a1a2a3a4
    e(i)00464
    l(i)03464

    关键活动是e(i)与l(i)相等的,所以关键活动是a0,a2,a3,a4

    实例2

     

    展开全文
  • AOE网活动的最早、最迟发生时间及关键路径问题

    万次阅读 多人点赞 2018-05-22 18:10:12
    上个学期学数据结构的时候有学到,这学期的离散数学又要考。。复习复习 有向图中,用顶点表示事件,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成...

    免费浏览请前往:https://zhuanlan.zhihu.com/p/337438327

    上个学期学数据结构的时候有学到,这学期的离散数学又要考。。复习复习

    有向图中,用顶点表示事件,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

    在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE(Activity On Edge)网,如图: 

    如何求AOE网中各事件(节点)和各活动(边)的最早开始时间和最迟开始时间以及工程的关键路径?

    整个活动的完成时间是AOE图中从始点到终点的最长路径的长度,这条路径称为关键路径。关键路径上的活动称作关键活动。

    注意:关键路径不一定只有一条。

    1.最早发生时间:从前往后,前驱结点到当前结点所需时间,取最大值。

    如上图中的节点4有两个前驱结点(节点2和3),节点2到节点4的最早发生时间是a1+

    展开全文
  • 文章目录一:关键路径基本概念(1)AOE网(2)AOV网和AOE网的对比(3)关键路径二:手动求解关键路径(1)每个事件(即顶点)的最早发生时间和最迟发生时间(2)每个活动(即边)的最早发生时间和最迟发生时间(3)...

    一:关键路径基本概念

    (1)AOE网

    AOE网(Activity On Edge Network):在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示和活动,用边上的权值表示活动的持续时间。其中没有入边的顶点称之为源点,没有出边的点称之为终点

    如下图就是一个AOE网,其中

    展开全文
  • 关键路径中早/迟发生时间

    千次阅读 多人点赞 2021-01-06 17:17:35
    2.事件Vi的最迟发生时间vl(i) 3.活动ai的最早发生时间e(i) 4.活动ai的最迟发生时间l(i) 例子: 求V4和a4的以上四个值(下面有全部活动和事件的参考) 1.事件Vi的最早发生时间ve(i):要找事件(即图中顶点)...

    概念:在AOE网中,顶点表示事件,弧表示活动,权表示活动持续的时间。一般求的是关键路径,而要求关键路径则要找到以下四个值

    • 1.事件Vi的最早发生时间ve(i)
    • 2.事件Vi的最迟发生时间vl(i)
    • 3.活动ai的最早发生时间e(i)
    • 4.活动ai的最迟发生时间l(i)
      例子:在这里插入图片描述

    求V4和a4的以上四个值(下面有全部活动和事件的参考)
    1.事件Vi的最早发生时间ve(i):要找事件(即图中顶点)的最早发生时间只需找到开始事件V0到该事件的最长路径即可,可以看到这里V0到V4有两条路,V0->V1->V4,权值为5,V0->V2->V4,权值为7,选其中最大的即为7,所以V4的最早发生时间为7天;

    2.事件Vi的最迟发生时间vl(i):最迟发生事件与上相反,要先找出最终事件的最长路径,为18,然后在减去从V8到V4中最长的路径,这里有V8<-V6<-V4,权值为11,V8<-V7<-V4,权值为11,得出最迟发生时间为18-11=7天,注意这里是要减去最长路径,也就是要找到最短的路径;

    3.活动ai的最早发生时间e(i):这里可以看到a4前面只有a1,所以活动ai的最早发生时间e(i)就是a1的值6(不包含自己的值);

    4.活动ai的最迟发生时间l(i):与事件Vi的最迟发生时间vl(i)相似,用最长路径18减去其中时间的最长路径,所以活动ai的最迟发生时间l(i)就是MIN(18-2-9-1,18-4-7-1)为6(包含了自己的值);

    以下为所有参考:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    参考书籍:数据结构C语言版

    展开全文
  • 书上求关键路径的时候利用了事件最早发生时间etv数组和事件最迟发生时间ltv数组,其中事件最迟发生时间ltv数组初始化为ltv[i]=etv[GL->numVertexes-1]。那假设有9个顶点,V8最后进栈(拓扑序列的最后一位),V9倒数...
  • 有几个基本的概念我们要先了解,在带权有向图中,顶点表示事件,有向边表示活动,以边上的权值表示活动的开销,比如完成活动所需要的时间。这样的网络称为用边表示活动的网络,也就是AOE网。 分清发生和开始 这里...
  • 数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么? 数据结构AOE网关键路径问题,不算活动差,直接看事件最迟最早差,差为0的就是关键路径,这样做对么?我做了几道...
  •   在思考这个问题之前,我们先来了解一下,在关键路径中,开始和发生有什么区别? 开始和发生   “发生”是针对于事件的,也就是...  刚开始我也很疑惑,为什么是最长的路径长度决定早的发生时间呢?难道不应该
  • 工作M的最迟开始时间为第23天(23+5=28,第28天要开始另外的工作了,所以最晚必须第23天开始),最早开始时间为第16天,所以总时差有7天。 最早完成工作M的时间是第21天,下次项目开始的最早是第25天,所以自由时差...
  • 这篇文章通过求aoe最早开始时间以及最迟开始时间来求关键路径 在求之前需要把图放到一个邻接链表之中 关键路径 关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的...
  • (1):根据各项活动的活动时间计算各个事件的最早时间最迟时间,并填入图中事件2-8相应位置。 (2):写出关键事件。 答:最早时间:从前往后计算; 最迟时间:从后往前计算。 关键事件:即开始时间和结束时间...
  • 关键路径:早开始时间 计算方式:每个节点找它到下个节点的最大路径 具有最大路径长度的路径为关键路径。因为你得保证每个人都到场才能去看电影嘛,那你肯定得等到最后一个人到了才能走。图中就是v...
  • AOE网活动和关键路径

    2011-07-04 20:36:05
    求出AOE网每个活动的最早开始时间最迟开始时间;该工程完成的最早时间以及判断出那些是关键路径。
  • 1)一个点的早/时间是有公式或者技巧求出来的 2)一个活动的晚开始几天不影响,或者一个活动可以耽搁的时间,是有公式计算的 3)关键路径为起点到终点权值加起来最大的路径 直接例题 首先,关键路径为最大...
  • 最短路径 在非网图中,最短路径是指两顶点之间经历的边数最少的路径。 在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。 一、Dijkstra算法 ...设置一个集合S存放已经...(一)事件的发生时间ve...
  • AOV 网: 强调的是在一个完整的过程中,各个活动所发生的顺序 其中用顶点表示活动,用弧表示活动之间的优先关系,例如:在 ???? 图中,活动 A 应该在活动 B 之前发生 把各个活动按照发生的先后顺序进行排序就称为...
  • 假设已经算好了事件 Vj1V_{j1}Vj1​ ~ VjkV_{jk}Vjk​ 的最迟发生时间vl[j1] ~ vl[jk],那么事件 ViV_iVi​的最迟发生时间就是vl[j1] - length[r1] ~ vl[jk] - length[rk] 中的最小值。此时取最小值是因为必须保证 ...
  • 关键路径

    2018-11-14 18:50:39
    在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网。AOE网中没有入边的顶点称为始点(或源点),没有出边的顶点称为...
  • 关键路径详解

    2021-09-16 09:12:59
    Ve事件的发生时间 发生时间是由最长路径决定的, 结点是事件,边是活动,一个事件C被两个活动a、b所指向,a活动耗时3、b活动耗时5,则c事件早要耗时5才能发生,因为事件C发生的前提是a、b两活动完成(可...
  • 数据结构图

    2018-09-26 19:22:30
    两种小生成树的生成方法;(普里姆算法(加点法),克鲁斯卡尔算法(加边法)) 各种求最短路径的方法;(迪杰斯特拉算法,弗洛伊德算法) 用顶点表示活动和用边表示活动的两种网络结构特点和相关操作的实现算法...
  • e=e->next) {//求各顶点事件的最迟发生时间ltv值 k=e->adjvex; if(ltv[k]-e->weight ltv[gettop] =ltv[k]-e->weight; } for(j=0;jnumVertexes;j++) { for(e=GL->adjList[j].firstedge;e;e=e->next) { k=e->adjvex; ...
  • ![图片](https://img-ask.csdn.net/upload/201512/06/1449378627_834004.jpg)
  • (2)计算出各个事件的最早发生时间与最迟发生时间,并显示输出; (3)输出所有的关键路径。 2、算法描述: 数据结构: typedef struct arc { int index; //编号 float weight; //权重 struct arc *next; //指向下...
  • 关键路径可以求出流程图中的最短时间,找到该流程图中的关键的路径,当该路径走完,流程也就结束了,表示该流程走完最短需要的时间,可以用来评估我们项目完成的时间。 二、相关概念 2.1 关键路径 这里举一个很...
  • 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为用边表示活动的网络,简称AOE网。AOE网和AOV网都是有向无环图,不同之处在于它们的边和顶点...
  • 关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(时间...
  • 图论 —— AOE 网与关键路径

    千次阅读 多人点赞 2019-06-06 12:33:37
    在表示一个工程时,用顶点表示事件,用弧表示活动,权值表示活动的持续时间,这样的有向图即为 AOE 网。 其有两个性质: 在顶点表示事件发生之后,从该顶点出发的有向弧所表示的活动才能开始。 在进入某个顶点的...
  • 【算法】基于AOE网的关键路径算法

    千次阅读 2017-09-28 15:58:21
    在工程上,我们都很讨厌工程的延期,同时一个工程由分为很多的节点,我们不知道哪些节点决定着这个工程是否会延期,每一个部分有没有可以伸缩的时间,于是,这个用来计划工程的关键路径算法就诞生了。看来,数据结构...
  • 一个事件的最迟发生时间为以该事件为尾的弧的活动最迟开始时间与该活动持续时间的差. D.关键活动一定位于关键路径 解:本题错误的主要原因是没有搞清楚** 弧头 与 弧尾 **的概念。 箭头所指,为** 弧头 。...
  • 2、最迟发生时间:从后往前,后继结点的最迟时间减去边权的值,取最小值; 结束节点的最早发生时间和最迟发生时间相同。 3、关键路径:最早发生时间和最迟发生时间相同的结点叫做关键路径上的结点; 4、最早开始...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,351
精华内容 8,540
关键字:

最迟发生时间