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

    万次阅读 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个表
  • AOE网中关键路径的一般求法

    千次阅读 2012-12-01 11:26:25
    预备知识 1、由于整个工程只有一个开始点,一个结束点...路径长度最长路径叫做关键路径。 由于在严蔚敏《数据结构》中有详细证明过程,我就不赘述啦,这里我只给出具体实现代码。 扩展阅读: 传送门:http:

    预备知识

    1、由于整个工程只有一个开始点,一个结束点,故在正常情况下(无环),网中只有一个入度为0的点和一个出度为0的点。

    2、与AOV网不同,AOE网中有些活动可以并行的进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径。

    由于在严蔚敏的《数据结构》中有详细的证明过程,我就不赘述啦,这里我只给出具体实现的代码。

    扩展阅读:

    传送门:http://blog.163.com/zhoumhan_0351/blog/static/3995422720098236028304/

    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <stack>
    using namespace std;
    
    const int MAXN = 1010;
    const int MAXM = 10010;
    
    struct Edge
    {
    	int v, w;
    	int id;
    	int next;
    }edge[MAXM];
    
    int n, m;
    int cnt;
    
    int first[MAXN], topo[MAXN];
    int ind[MAXN], outd[MAXN];
    int tot;
    int Ee[MAXN], El[MAXN], E[MAXN], L[MAXN];
    /*Ee表示事件最早可能发生时间,El表示事件最迟允许发生时间*/
    /*E表示活动最早可能发生时间,L表示活动最迟允许发生时间*/
    
    void init()
    {
    	cnt = 0;
    	tot = 0;
    	memset(first, -1, sizeof(first));
    	memset(ind, 0, sizeof(ind));
    	memset(outd, 0, sizeof(outd));
    	memset(Ee, 0, sizeof(Ee));
    	memset(E, 0, sizeof(E));
    	memset(L, 0, sizeof(L));
    }
    
    void read_graph(int u, int v, int w, int id)
    {
    	edge[cnt].v = v, edge[cnt].w = w, edge[cnt].id = id;
    	edge[cnt].next = first[u], first[u] = cnt++;
    }
    
    void toposort() //拓扑排序 
    {
    	queue<int> q;
    	for(int i = 0; i < n; i++) if(!ind[i]) q.push(i);
    	while(!q.empty())
    	{
    		int x = q.front(); q.pop();
    		topo[++tot] = x;
    		for(int e = first[x]; e != -1; e = edge[e].next)
    		{
    			int v = edge[e].v, w = edge[e].w;
    			if(--ind[v] == 0) q.push(v);
    			if(Ee[v] < Ee[x] + w) //求出各个顶点Ee值 
    			{
    				Ee[v] = Ee[x] + w;
    			}
    		}
    	}
    }
    
    void CriticalPath()
    {
    	toposort();
    	int top = tot;
    	int Max = 0;
    	for(int i = 0; i < n; i++) Max = max(Max, Ee[i]); //注意,初始化时为Ee中的最大值,否则会报错。 
    	for(int i = 0; i < n; i++) El[i] = Max; 
    	while(top) //逆拓扑排序求顶点El的值 
    	{
    		int x = topo[top--];
    		for(int e = first[x]; e != -1; e = edge[e].next)
    		{
    			int v = edge[e].v, w = edge[e].w;
    			if(El[x] > El[v] - w)
    			{
    				El[x] = El[v] - w;
    			}
    		}
    	}
    	for(int u = 0; u < n; u++) //求出E,L关键活动 
    	{
    		for(int e = first[u]; e != -1; e = edge[e].next)
    		{
    			int v = edge[e].v, id = edge[e].id, w = edge[e].w; //id代表活动的标号 
    			E[id] = Ee[u], L[id] = El[v] - w;
    			if(E[id] == L[id]) //相等一定是关键活动 
    			{
    				printf("a%d : %d->%d\n", id, u, v);
    			}
    		}
    	}
    }
    
    void read_case()
    {
    	init();
    	for(int i = 1; i <= m; i++)
    	{
    		int u, v, w;
    		scanf("%d%d%d", &u, &v, &w);
    		read_graph(u, v, w, i); //read_graph
    		outd[u]++, ind[v]++;
    	}
    }
    
    int main()
    {
    	while(~scanf("%d%d", &n, &m))
    	{
    		read_case();
    		printf("\nThe Critical activities are:\n");
    		CriticalPath();
    	}
    	return 0;
    }
    
    
    /*
    input :
    9 11
    0 1 6
    0 2 4
    0 3 5
    1 4 1
    2 4 5
    3 5 2
    4 6 9
    4 7 7
    5 7 4
    6 8 2
    7 8 4
    */
    
    /*
    output:
    a2 : 0->2  //a1 : 0->1
    a5 : 2->4 //a4 : 1->4
    a8 : 4->7
    a7 : 4->6
    a10 : 6->8
    a11 : 7->18
    */
    	
    
    


    展开全文
  • 数据结构,使用C语言编写的求关键路径的源代码
  • 关键路径

    2020-03-09 17:26:18
    关键路径的求法一般是针对有向无环图的,常用来解决工程中的问题,前面我们学过Bellman和SPFA算法,如果我们给每条边变成相反数就可以求解关键路径了,当然关键路径不止一种求法,数据结构中给出的关键路径求法的...

    关键路径的求法一般是针对有向无环图的,常用来解决工程中的问题,前面我们学过Bellman和SPFA算法,如果我们给每条边变成相反数就可以求解关键路径了,当然关键路径不止一种求法,数据结构中给出的关键路径求法的优势在于其更快,利用了ve,vl数组,下面是其代码。

    #include<iostream>
    #include<stack>
    #include<queue> 
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    const int maxv=1001;
    
    struct node{
    	int v,w;
    };
    vector<node>Adj[maxv];//定义邻接表
    int indegree[maxv];//存储入度 
    
    int ve[maxv],vl[maxv];
    stack<int>s;//存储拓扑排序,逆向输出为逆拓扑排序
    
    
    bool topological(int n) {  //拓扑排序,生成事件最早开始时间 
    	fill(ve,ve+n+1,0);//从前向后推 
    	queue<int>q;
    	for(int i=1;i<=n;i++) 
    	if(indegree[i]==0)
    	q.push(i);
    	while(!q.empty()){
    		int t=q.front();q.pop();
    	    s.push(t);
    	    for(int i=0;i<Adj[t].size();i++){
    	    	int x=Adj[t][i].v,w=Adj[t][i].w;
    	    	indegree[x]--;
    	    	if(indegree[x]==0)
    	    	q.push(x);
    	    	if(ve[t]+w>ve[x])//x位置的最早时间等于之前最长的路 
    	    	ve[x]=ve[t]+w;
    		}
    	}
    	if(s.size()==n)return true;
    	return false;
    }
    
    
    int createvl(int n) {//生成事物的最迟开始时间 
       int maxlength=0;
       for(int i=1;i<=n;i++)   //找到汇点 
       if(ve[i]>maxlength)
       maxlength=ve[i];
    	fill(vl,vl+n+1,maxlength);//从后往前推 
    	while(!s.empty()){
    		int t=s.top() ;s.pop(); 
    		for(int i=0;i<Adj[t].size();i++)
    		{   
    		    int x=Adj[t][i].v;
    			if(vl[x]-Adj[t][i].w<vl[t]) 
    			//t处最迟开始时间等于 之后路径最迟开始时间的最小值 
    			vl[t]=vl[x]-Adj[t][i].w;
    		}
    	}	
    	return maxlength;
    }
    
    
    int criticalpath(int n) {
    	
    	if(topological(n)==false)
    	return-1;
     int  k=createvl(n);
    	
    	for(int i=1;i<=n;i++)
    	for(int j=0;j<Adj[i].size();j++){
    		int x=Adj[i][j].v,w=Adj[i][j].w;
    		int e=ve[i],l=vl[x]-w;
    		if(e==l)
    		printf("%d->%d\n",i,x);
    	}
    	return k; //返回路径和 
    }
    
     int main(){
     	int n,m,x,y,w;
     	scanf("%d%d",&n,&m);
     	node t;
     	fill(indegree,indegree+n+1,0);
     	for(int i=1;i<=m;i++){
     		scanf("%d%d%d",&x,&y,&w);
     		t.v=y;t.w=w;
     		Adj[x].push_back(t);
     		indegree[y]++;
    	 }
    	 criticalpath(n);
     	
     	return 0;
     }
    

    还有动态规划也可以求关键路径,等接下来学习之后补充。

    展开全文
  • 题目如下图: ...事件最早发生事件求法:找从原点到该事件最长路径(从前往后推) 对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 }...

    题目如下图:

    注:将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

            其他类似

    综上所述,可得下表:

        

    事件 a b c d e f
    Ve 0 19 15 29 38 43
    Vl 0 19 15 37 38 43

     

    活动 ab ac cb bd be ce df ef
    权值 2 15 4 10 19 11 6 5
    e 0 0 15 19 19 15 29 38
    l 17 0 15 27 19 27 37

    38

     

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

    转载于:https://www.cnblogs.com/DSYR/p/9217126.html

    展开全文
  • DAG最长路径求法

    2020-05-03 11:16:17
    所谓DAG就是有向无环图,利用关键路径的做法有些复杂。 我们建立一个数组dp[n+1], dp[i]代表从这个结点出发的最长路径, 那么要求出dp[i], 我们只要求出从i出发的下一结点的dp[j], 使得dp[i] = max(dp[i], dp[j] + G...
  • 指正错误,或者认为我写对不对,手机拍比较小,见谅!!![图片](https://img-ask.csdn.net/upload/201512/11/1449821168_88531.jpg)![图片](https://img-ask.csdn.net/upload/201512/11/1449821248_167435.jpg)
  • 关键路径法及C语言实现

    千次阅读 2020-03-19 08:55:50
    在学习拓扑排序一节时讲到拓扑排序只适用于 AOV 网,本节所介绍的求关键路径针对的是和 AOV 网相近的 AOE 网。 AOE网 AOE 网是在 AOV 网的基础上,其中每一个边都具有各自的权值,是一个有向无环网。其中权值表示...
  • 1.实验目的 熟悉图的数组表示法和邻接表存储结构,掌握构造有向图和无向图的算法,在掌握以上知识的基础上,熟悉图...(4)在邻接表上实现拓扑排序、关键路径的求法,在邻接矩阵上实现最短路径,最小生成树的求法 ...
  • :公交乘客出行路径选择是公交乘客信息系统的关键技术,提出以换乘次数最少为首要目标、出行距离 最短为第二目标算法,本算法是基于广度优先搜索并结合蚂蚁算法提出公交路线最短路径选择新算法 关键词:最短路径...
  • 这篇文章通过aoe最早开始时间以及最迟开始时间来求关键路径之前需要把图放到一个邻接链表之中 ...在优化设计过程中关键路径法可以反复使用,直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器...
  • 关键路径,只需理解顶点(事件)和边(活动)各自两个特征属性以及求法即可:  Ø 先根据首结点Ve(j)=0由前向后(正拓扑序列)计算各顶点最早发生时间  Ø 再根据终结点Vl(j)等于它Ve(j)由后向前...
  • 题意:给出一个图,要求删除一些边,然后使得删除后图是一颗树,并且各个点到0点距离为原来图中最短距离,有多少种删最短路出根到每个点距离,然后遍历每一个点,找到满足最短路的关键路径数:d[i] + ...
  • 顺序图):节点表示活动,箭线表示逻辑箭线图(也叫双代号网络图):节点无实际意义,只表示活动开始和结束,箭线同时表示任务和逻辑关系一般求关键路径时,用前导图六标时,总时差等于0或者小于0活动组成关键...
  • 求解AOE网关键路径时,书上方法为先从源点到汇点求解事件最早发生时间ve,再从汇点到源点求解事件最迟发生时间vl,再利用ve和vl求解每个活动最早开始时间e(i)和最迟开始时间l(i),e(i)和l(i)相等活动则为关键...
  • 在学习数据结构部分时对图应用(最短路径和关键路径)特别困惑,所以总结了笔记,并分享出来,特别是蓝色和红色字体。有问题请及时联系博主:Alliswell_WP,转载请注明出处。 重点难点:图应用(最短路径和关键...
  • 关键路径法将项目分解成为多个独立活动并确定每个活动工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目工期、各个活动时间特点(最早最晚时间、时差)等。...
  • 首先贴一下百度百科对CPM定义:关键路径法(Critical Path Method, CPM)是一种基于数学计算项目计划管理方法,是网络图计划方法一种,属于肯定型网络图。关键路径法将项目分解成为多个独立活动并确定每个...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 156
精华内容 62
关键字:

关键路径的求法