精华内容
下载资源
问答
  • 关键路径求

    万次阅读 多人点赞 2018-03-26 13:15:05
    关键路径概念: 在无回路的有向网络中,假设只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点),则从源点到汇点之间的最长的路径称为关键路径。AOE网: 无回路有向网络可以用来表示一个包含多项活动的...

    关键路径概念:

          在无回路的有向网络中,假设只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点),则从源点到汇点之间的最长的路径称为关键路径。

    AOE网:

        无回路有向网络可以用来表示一个包含多项活动的工程计划:有向边表示一项活动,边上的权表示完成这项活动需要的时间;顶点表示"所有入边代表的活动已完成,出边代表的活动可以开始"这样一种状态或者事件,其中源点表示工程的开始,汇点表示工程的结束;源点到汇点的某一关键路径上边的权值之和表示完成整个工程的计划时间。

        通过求有向网络的关键路径,可以算出整个工程从开始到结束至少需要多少时间;可以知道哪些活动是影响工程进度的关键活动。

        这种用边表示活动且只有一个源点和一个汇点的无回路有向网络称为边表示活动的网,简称AOE网。

    两个与顶点有关的量:

        在下面的讨论中,假定AOE网有n个顶点,源点是V1,汇点是Vn。

        -最早发生时间:

            事件Vi的可能的最早发生时间earliest(i),它等于从源点V1到顶点Vi的最长路径长度。

        -最迟发生时间

            在保证汇点事件Vn在earliest(n)时刻发生的前提下,事件Vi允许的最迟发生时间latest(i),它等于earliest(i)减去从顶点Vi到汇点Vn的最长路径长度。

    earliest数组的计算方法:

        -令earliest(1)=0;

        -按顶点的拓扑顺序计算earliest(j):

            earliest(j)=max{(earliest(i)+Wij)|Vi邻接到Vj}

        -例如

            earliest(a)=max{earliest(b)+u,earliest(c)+v}

    latest数组的计算方法:

        -令latest(n)=earliest(n);

        -按顶点的逆拓扑顺序计算latest(i):

            latest(i)=min{(latest(j)-Wij)|Vj邻接于Vi}

        -例如:

            latest(a)=min{latest(d)-x,latest(e)-y}

    两个与边有关的量:

        对于活动ak=<Vi,Vj>,可以定义它的可能的最早开始时间和允许的最迟开始时间。

        -最早开始时间:活动ak的可能的最早开始时间等于事件Vi的可能的最早发生时间earliest(i)

        -最迟开始时间:活动ak的允许的最迟开始时间等于事件Vj的允许的最迟发生时间latest(j)减去完成该活动的计划时间Wij。

       

    (最早发生,从前往后算;最迟发生,从后往前算。)


     

    求关键路径的算法:

        1、计算每个事件可能的最早发生时间

    //计算每个事件可能的最早发生时间
    template<class T>
    void ExtLGraph<T>:: Earliest(int* earliest, int* order)
    {
        for(int i=0;i<n;i++)  earliest[i]=0;
         for(i=0;i<n;i++){
    	    int k=order[i];
    	    for (ENode<T>* p=a[k]; p; p=p->nextArc){
                int  j=p->adjVex;
    	    if (earliest[j]<earliest[k]+p->w) 
    	  	  earliest[j]=earliest[k]+p->w;
            }
      }
     }

        2、计算每个事件允许的最迟发生时间

    //计算每个事件允许的最迟发生时间
    template<class T>
    void ExtLGraph<T >:: Latest(int* latest,int* order,int longest)
    {
    	for (int i=0;i<n;i++) latest[i]=longest;
        for (i=n-2;i>-1;i--){
            int j=order[i]; 
               for (ENode<T>* p=a[j];p;p=p->nextArc) {
                   int  k=p->adjVex;
       if (latest[j]>latest[k]-p->w)
    		  latest[j]=latest[k]-p->w;
    }
         }
     }
    

        3、输出关键活动

    最早发生时间和最迟发生时间相等的事件,一般就是关键活动。

    从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动称为关键活动。



    展开全文
  • 关键路径 拓扑排序 C语言 建立邻接表时 用了2个表 实在有点说不过去 其实计算入读 在建立的时候可以计算出来 没有必要用2个表
  • 题目如下图:事件最早发生事件法:找从原点到该事件的最长路径(从前往后推) 对a:Ve=0 对b:Ve=max{ 2 , 15+4 }=19 对c:Ve=15 对d:Ve=19+10=29 对e: Ve=max{ 19+19,15=17 }=38 对f:Ve=38+5=43事件最...

    题目如下图:


    注:将123456当成abcdef.

    事件最早发生事件求法:找从原点到该事件的最长路径(从前往后推)

            对a:Ve=0    

            对b:Ve=max{ 2 , 15+4 }=19

            对c:Ve=15

            对d:Ve=19+10=29

            对e:   Ve=max{ 19+19,15=17 }=38        对f:Ve=38+5=43

    事件最晚发生时间求法:找从终点到该事件的最长路径,再做减法(从后往前推)        

             对f:Vl=43

             对e:   Vl=43-5=38

             对d:Vl=43-4=39

             对c:Vl=min{ 43-(10+6+4), 43-(5+19+4), 43-(5+11) }=15

            对b:Vl=min{ 43-(10+6) , 43-(19+5) }=19

            对a:Vl=0 

    活动(弧)的最早开始时间求法:取决于活动头端点的事件发生的最早时间

            对ab:E=Ve(a)=0        对ac:E=Ve(a)=0

            对be:E=Ve(b)=19     对bd:  E=Ve(b)=19

            对cb:   E=Ve(c)=15     对ce:   E=Ve(c)=15

            对df:E=Ve(d)=29     对ef:    E=Ve(e)=38

    活动(弧)的最晚开始时间求法:取决于尾端的Vl,再减去弧的权值 

            对ab:L=Vl(b)-2=17        对ac:L=Vl(c)-15=0

            其他类似

    综上所述,可得下表:

        

    事件abcdef
    Ve01915293843
    Vl01915373843
    活动abaccbbdbecedfef
    权值215410191165
    e00151919152938
    l1701527192737

    38

    关键路径即e与l相等的路径:<a,c>,<c,b>,<b,e>,<e,f>

           


    展开全文
  • 请帮我检查一下!!!指正错误,或者认为我写的对不对,手机拍的比较小,见谅!!![图片](https://img-ask.csdn.net/upload/201512/11/1449821168_88531.jpg)![图片]...
  • #include "stdafx.h" #include"malloc.h" typedef int Status; typedef int InfoType;... printf("以下是查找图的关键路径的程序。\n"); TopologicalOrder(G,T); CriticalPath(G); return 0; }
  • AOE网络关键路径

    2012-07-09 02:54:44
    用C++实现的代码,AOE网络的关键路径,有详细注释
  • AOE 求关键路径 程序

    2010-12-02 17:49:27
    本程序用c#编写,实现了建图,利用AOE实现求解关键路径问题,并标明那些路径为关键路径
  • 求关键路径

    千次阅读 2015-03-30 10:37:52
    求关键路径 1、重要概念  (1)AOE (Activity On Edges)网络 如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(Activity),用边上的权值表示活动的持续时间(Duration),用顶点表示事件...

    求关键路径

    1、重要概念

               1AOE (Activity On Edges)网络 如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(Activity),用边上的权值表示活动的持续时间(Duration),用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络,简称AOE (Activity On Edges)网络。AOE网是一个带权的有向无环图。

    AOE网络在某些工程估算方面非常有用。例如,可以使人们了解:

        a、完成整个工程至少需要多少时间(假设网络中没有环)?

         b、为缩短完成工程所需的时间应当加快哪些活动

         (2关键路径(Critical Path) AOE网络中有些活动顺序进行,有些活动并行进行。从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)

          如果一个活动的最早开始时间等于它的最迟开始时间,那么这个活动就被称为是关键活动,关键活动连接在一起就是关键路径。

    如图1就是一个AOE网,该网中有11个活动和9个事件。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如事件v5表示a4a5活动已经完成,a7a8活动可以开始。每个弧上的权值表示完成相应活动所需要的时间,如完成活动a1需要6天,a8需要7天。

    14、求关键路径 - 墨涵 - 墨涵天地

    1

           AOE网常用于表示工程的计划或进度。由于实际工程只有一个开始点和一个结束点,因此AOE网存在唯一的入度为0的开始点(又称源点)和唯一的出度为0的结束点(又称汇点),例如图1AOE网从事件v1开始,以事件v9束。同时AOE网应当是无环的。

    3)算法描述中要用到的几个表达

    e(i)表示活动ai的最早开始时间,l(i)表示活动ai的最迟开始时间; l(i)-e(i)表示完成活动的时间余量。事件vi 的最早开始时间表示为ve(i), 事件vi 的最迟允许开始时间vl(i)

    l[k] = e[k]的活动就是关键活动。为求得e[k]l[k],需要先求得从源点v0到各个顶点vi  ve[i]  vl[i]。如果活动a由弧<j,k>表示,其持续时间记为dut(<j,k>),则有如下关系:          
            e(i)=ve(j)
            l[i] = vl[k] – dut(<i, k>)

    ve(j)vl(j)需分两步进行:

    1

    14、求关键路径 - 墨涵 - 墨涵天地

    其中, T是所有以第j个顶点为头的弧的集合。

    2

    14、求关键路径 - 墨涵 - 墨涵天地

    其中, S是所有以第i个顶点为尾的集合。

    这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。也就是说,ve(j-1)必须在v的所在前驱的最早发生时间求得之后才能确定,而vl(j-1)则必须在v的所有后继的最迟发生时间求得之后才能确定。因此,可以在拓扑排序的基础上计算ve(j-1)vl(j-1)

    2、需要说明的地方

    1)上面的图1中的关键路径就为

    14、求关键路径 - 墨涵 - 墨涵天地

    2)影响关键活动的因素是多方面的,任何一项活动持续时间的改变都会影响关键路径的改变。关键活动的速度提高是有限度的,只有在不改变网的关键路径的情况下,提高关键活动的速度才有效。如果网中有几条关键路径,那么单是提高一条关键路径上的关键活动的速度,还不能导致整个工程缩短工期,而必须同时提高几条关键路径上的活动的速度。


    更通俗地来理解:

     
    在这种AOE网中, 最长的一条路径就是关键路径 ,因为图中每个活动都是必须的,只有最长的工期完成后,项目才真正完成了,图中10+9+20+10 也就是ADFHJ  ,显然是最长的,所以为关键路径

    从左边开始每个活动所需要最长的时间就是 最早开始时间 ,如C,只有A指向它,那么最早开始时间就是5;F, A->C->F
    5+4=9, A->D->F  10+9=19,两者比较,后者大,故19为最早开始时间,依次类推。

    从右边倒推,可以求的 最迟开始时间, 如J为49,以I为例,I->J 倒推 49-4=45 所以I最迟开始时间为45;H为例,H->J 倒推49-10=39,H->I->J 倒推 49-4-1=44,两者取最小的,所以H的最迟开始时间为39。

    展开全文
  • AOE求关键路径

    千次阅读 2019-12-03 18:26:20
    在AOE图,一个事件发生的要求是通向其的活动全部结束,那么这么时间发生的最早时间就是与之相连的所有活动全部结束后的时间,而关键路径就是,使得事件都发生的路径。这个路径的时间一定是最长的。 基本思想 1.可以...

    AOE

    AOE图就是将节点作为事件,而中间的弧作为活动,权是活动持续的时间。

    关键路径

    在AOE图,一个事件发生的要求是通向其的活动全部结束,那么这么时间发生的最早时间就是与之相连的所有活动全部结束后的时间,而关键路径就是,使得事件都发生的路径。这个路径的时间一定是最长的。

    基本思想

    1.可以利用邻接矩阵的方式存储元素之间是否相连
    2.在使用一个数组记录节点的入度
    3.一个记录每个节点关键路径的字符串数组
    首先判断入读和和出度为零的节点,分别记为tail,head。
    将tail入队,然后,遍历以队首元素为tail的弧,若是不为无穷或则0,就将head的入度减一,知道入度为0就入队,直到队为空就结束。

    实现代码

     while(!all.empty())    //all为队列
        {
            int j=all.front();
            all.pop();
            for(int i=1;i<=a;i++)
            {
                if(p[j][i]!=9999)
                {
                    if(v[j]+p[j][i]>v[i])
                    {v[i]=v[j]+p[j][i];
                      path[i]=path[j];
                      path[i].push_back(48+j);
                    }
                      l[i]--;
                      if(l[i]==0)
                      {
                          all.push(i);    //入队就说明所有通过他的路径都以遍历结束,并且选出最长路径
                      }
                }
            }
        }
    
    展开全文
  • 关键路径

    千次阅读 多人点赞 2017-02-28 10:41:47
    关键路径
  • AOE 求关键路径程序

    2010-12-02 17:55:02
    本程序实现了根据你所输入的数据建图,并利用AOE出最长路径长度,并标明关键路径
  • 【笔记】AOE网与关键路径

    万次阅读 多人点赞 2017-12-02 01:06:32
    AOE网 关键路径 求关键路径的算法实现
  • 图的关键路径

    2018-06-21 11:02:02
    问题描述:设计一个程序出完成整项工程至少需要多少时间以及整项工程中的关键活动。 要求: 1)对一个描述工程的AOE网,应判断其是否能够顺利进行; 2)若该工程能顺利进行,输出完成整项工程至少需要多少时间,...
  • C语言AOE网关键路径

    2010-05-24 16:03:07
    这个程序为实现AOE求关键路径的程序,工具为VC,语言为C,内有readme,
  • 图:求关键路径

    千次阅读 多人点赞 2017-07-19 16:34:56
    一:概念:在学习关键路径前,先了解一个AOV网和AOE网的概念:如下图所示 假如汽车生产工厂要制造一辆汽车,制造过程的大概事件和活动时间如上图AOE网: 那么,显然对上图AOE网而言,所谓关键路径:开始–>发动机...
  • AOE网求关键路径

    千次阅读 2014-08-05 11:23:06
    下表给出了某工程各工序之间的优先关系和各工序所需的时问(其中“一”表示无先驱工序),请完成...(3) 关键路径并指明完成该工程所需的最短时间。 工序代号 A B C D
  • 有良好界面的JAVA编写的AOE网络关键路径,比较完善
  • 关键路径算法

    2012-12-25 01:39:19
    利用邻接表,拓扑排序关键 用邻接表实现关键路径
  • 关键路径C++

    2012-10-05 10:30:32
    (1) 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径; (2) 只有缩短关键活动的工期才有可能缩短工期; (3) 若一个关键活动不在所有的关键路径上,减少它并不能减少工期; (4) 只有在不改变...
  • 动规求关键路径.pdf

    2009-05-30 22:13:52
    基于动态规划思想求解关键路径的算法 刘 芳,王 玲 摘 要:关键路径通常是在拓扑排序的基础上求得的。提出了一种利用图的广度优先搜索与动 态规划算法相结合求解关键路径的新算法,该算法采用图的邻接表结构形式,不...
  • AOE网与关键路径

    千次阅读 2018-08-20 10:19:51
    求关键路径的算法实现     AOE网是以边表示活动的有向无环网,在AOE网中,具有最大路径长度的路径称为关键路径关键路径表示完成工程的最短工期。 1.AOE网   AOE网是一个带权的有向无环图。其中用顶点表示...
  • 拓扑图关键路径

    2014-06-15 19:48:11
    求解关键路径往往用于在AOE网图中从起始点到结束点做完所有事所需要的最小时间 求解关键路径的具体算法如下: (1)从开始顶点v0出发,假设开始顶点最早开始时间ve(0) = 0,然后按照拓扑有序出其它各顶点i的最早...
  • 关键路径(1)

    2014-02-25 17:26:09
    http://blog.csdn.net/h1023417614/article/details/17881187这个网址的代码是求某点的到...而关键路径求的是最长路径。 只要把上个网址的代码稍微改改即可    for ( i = 0; i  { cin>>spot1>>spot2>>len;  
  • JSP中求关键路径算法及java实现

    千次阅读 2015-05-17 17:03:10
    在JSP问题中,关键路径决定着车间作业的完工时间,通过引入基于关键路径的邻域规则,使邻域解大大减少,从而大大减少优化过程的复杂度。 关键块是关键路径中工序在同一台机器连续组成的工序集合。
  • 数据结构 课程设计说明书 基于 AOE网络的关键路径问题 学院部 计算机科学与工程学院 专业班级 学 号 学生姓名 指导教师 年 月 日 安徽理工大学课程设计论文任务书 计算机科学与工程 学院 学 号 学生姓名 专业班级 ...
  • 关键路径求解.cpp

    2020-01-28 17:02:18
    功能描述:对于任何大型工程项目(不少于10个活动),关键路径。 设计要求: 1)输入活动持续时间、结点编号。 2)输出关键活动、图形化关键路径

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,328
精华内容 21,331
关键字:

关键路径怎么求