精华内容
下载资源
问答
  • 有良好界面的JAVA编写的AOE网络求关键路径,比较完善
  • AOE求关键路径(关键活动): AOE网求解关键路径,所需的是有向无环图,注意的是,只有一个源点,有一个汇顶点,然后关键路径不一定只有一条。注意,这里要理解: 顶点:事件 边:活动 还有四个数组下面有介绍: ...

    AOE网求关键路径(关键活动):

    AOE网求解关键路径,所需的是有向无环图(利用拓扑排序,如果序列长度为顶点数,则是无环,小于顶点数则是有环图,有环图是不满足求AOE网的),注意的是,只有一个源点,有一个汇顶点,然后关键路径不一定只有一条。注意,这里要理解:

    顶点:事件
    边:活动

    还有四个数组下面有介绍:
    在这里插入图片描述
    在这里插入图片描述
    这里我们用到的图:

    关键活动已经用红色标记出来
    在这里插入图片描述

    代码如下:

    #include <stdio.h>
    #include <malloc.h>
    #define inf 330 
    #define max 50
    typedef struct node{
    	int adjvex;
    	int weight; //权值 
    	struct node *nextarc;
    }arcnode;//定义结点的结构体类型 
    
    typedef struct {
    	arcnode *firstarc;
    	int count; 
    }vnnode; //定义头结点的结构体 
    
    typedef struct {
    	vnnode  adjlist[max];
    	int n;
    	int e; 
    }adjgraph; //定义图表的结构体类型 
    
    typedef struct{
    	int sno;
    	int lno;
    }keynode; //关键活动 
    
    
    //创建邻接图 
    void createadj(adjgraph *&g, int a[max][max], int n, int e)
    {
    	arcnode *p;
    	
    	//分配一段空间,并做相应的赋值操作。 
    	g = (adjgraph *)malloc(sizeof(adjgraph));
    	g->n = n;
    	g->e = e;
    	
    	//对头结点初始化为NULL 
    	for(int i = 0 ;i <n; i++)
    	{
    		g->adjlist[i].firstarc = NULL;
    		g->adjlist[i].count = 0;
    	}
    	
    	 //循环找结点 
    	for(int i =0; i<n; i++)
    	 for(int j = n-1; j>=0; j--)
    	 	 if(a[i][j]!=0 && a[i][j]!=inf)//如果有边 
    		 {
    		 	p = (arcnode *)malloc(sizeof(arcnode));
    		 	p->adjvex =j;
    		 	p->weight = a[i][j];
    		 	g->adjlist[j].count++;
    		     
    		    //这里采用头插发 
    		 	p->nextarc = g->adjlist[i].firstarc;
    			g->adjlist[i].firstarc = p;  
    		  } 
     } 
     
    
    //输入图的邻接表 
     void showadj(adjgraph *g)
     {
     	arcnode *p;
     	for(int i =0; i< g->n; i++)
     	{
     		//首先指向头结点。 
     		p = g->adjlist[i].firstarc;
     		printf("%d 入度:(%d): ",i,g->adjlist[i].count);
     		
     		//这里是循环输出每个头结点的链表 
     		while(p!=NULL)
     		{
     			printf("%d -->",p->adjvex);
     			p = p->nextarc;
    		 }
    		 printf("/\\");
    		 printf("\n"); 
    	 }
     }
     
    
    //拓扑排序输出 
    /*算法的主要思想,一个是找入度为0的顶点进栈,二个每次出栈一个顶点,
    就要遍历其他相关有边的顶点,修改顶点入度,并判断是否入栈,不满足就寻找下一个相关有边的顶点。 
    */ 
    int  tp(adjgraph *g,int toplist[]) //参数数组toplist是用来保存拓扑序列的,用来判断是否成环 
    {
    	arcnode *p;
    	
    	//定义一个数组栈以及数组下标 
    	int st[max]; 
    	int top = -1; 
    	int d=0;
    	
    	int j,k;//定义两个变量,下面需要用到 
    	
    	//这个循环用来遍历所有点,找到入度为0的点将其进栈。 
    	for(int i=0; i<g->n; i++)
    	  if(g->adjlist[i].count ==0)
    	  {
    	  	 top++;
    	  	 st[top] = i;
    	   } 
    	   
    	 //在栈不空的情况下,出栈一个顶点,然后将这个顶点的所有有边的另外一端的顶点循环判断,如果入度为0,则进栈。遍历完之后接着出栈一个顶点,在遍历....循环同样的操作 
    	 while(top>-1)
    	 {
    	 	//出栈一个顶点 
    	   k = st[top--];
    	   toplist[d++]=k;
    	   printf("%d ",k);
    	   
    	   //在遍历该出栈顶点的其他有边的顶点 
    	   p = g->adjlist[k].firstarc;
    	   while(p!=NULL)
    	   {
    	   	 //度数-1 
    	   	   j = p->adjvex;
    		   g->adjlist[j].count--;
    		   
    		   //在判断是否可以入栈 
    			if(g->adjlist[j].count == 0 )
    			{
    				top++;
    				st[top] =j;
    			} 
    			
    		//遍历下一个顶点。 
    		 p =p ->nextarc;
    	   }
    	 }
        return d; //返回拓扑数组的长度 ,注意下标 
     } 
     
     
     //aoe求关键活动 
     /*算法的主要思想是求出事件的最早开始时间,(ve[max])
     事件的最迟开始时间,(vl[max])
     活动的最早开始时间,(ea[max])
     活动的最迟开始时间。(el(max))
      然后用一个结构体数组保存关键活动以及两端的顶点。 
     */ 
     bool aoesearch(adjgraph *g, keynode ky[max], int &d)///结构体数组,以及下标d 
     {
     	arcnode *p;
    
        int toplist[max]; //这里用来保存调用拓扑排序函数是保存拓扑序列 
        
     	int w;
     	
     	int ve[max]; //用来保存事件(顶点)最早开始时间 
     	int vl[max];//用来保存事件(顶点)最迟开始时间 
     	
     	int length = tp(g,toplist);//拓扑排序 
     	
        if(length  < g->n) //拓扑排序长度若小于顶点数,则说明有回路 
        return false;
        
        int inode = toplist[0]; //找打源点 
        int lnode = toplist[g->n-1];//找到汇点 
       
       
    	//初始化,每个事件的最早开始时间为0 
    	for(int i=0;i< g->n; i++)
    	{
        	ve[i] = 0;	
    	}
    	//找每个事件的最早开始事件。(找最大) 
    	for(int i =0; i<g->n; i++)
    	{
    		p = g->adjlist[i].firstarc;
    		while(p!=NULL)
    		{
    		    w = p->adjvex;
    			if(ve[i]+ p->weight> ve[w])
    			  ve[w] = ve[i]+ p->weight;
    			p = p->nextarc;
    		}
    	}
    	
    	//初始化,每个事件的最晚开始事件为汇点的最早开始时间 
    	for(int i =0; i<g->n; i++)
    	   vl[i] = ve[lnode];
    	   
    	//逆序找每个事件的最晚开始事件(找最小) 
    	for(int i= g->n-2; i>=0; i--)//
    	{
    		p = g->adjlist[i].firstarc;
    		while(p!=NULL)
    		{
    			w = p->adjvex;
    			if( vl[w] - p->weight <vl[i])
    				vl[i] = vl[w] - p->weight;
    			p = p->nextarc;
    		}
    	}
    
        //找关键活动((存储到结构体数组中)
        for(int i =0; i<g->n; i++)
    	{	
    		p = g->adjlist[i].firstarc;
    		
    		while(p!= NULL)
    		{
    			w = p->adjvex;
    			//注意,由于没定义活动(边)的最早开始时间ae[i]和最迟开始时间al[j],这里ae[i] = i,al[i] = vl[w] - p->weight,这里的ae和al表示活动的最早开始时间和最迟开始时间。 
    			if(ve[i] == (vl[w] - p->weight)) 
    			{
    				d++;
    				ky[d].sno = i;
    				ky[d].lno = w;
    			}
    		 p = p->nextarc; 
    		}
    	}   	  
    	return true;  
    }
    void showpath(adjgraph *g, keynode ky[],int d)
    {
       
    	arcnode *p;
    	int w;
    	int length =d;
        
    	for(int i =0; i<g->n; i++)
    	{
    		p = g->adjlist[i].firstarc;
    		
    		     while(p!=NULL)
    	     	{
    	     		
    		    	w = p->adjvex;
    		    	for(int j =0; j<=length; j++)  //这里之所以等于0,是因为d是从-1开始,第一个值的下标就是0,而不是从0开始,第一个值下标是1; 
    			    if(i == ky[j].sno && w == ky[j].lno)
    			    {
    			    	printf("(%d,%d):%d  \n",i,w,p->weight);
    				}
    				p = p->nextarc;
    		    }
    			
    		
    	}
    }
    
    int main() 
    {
    	adjgraph *b;
    	int d=-1; //用于结构体数组的下标 
    	
    	keynode ky[max];
    	int toplist[max];
    	
    	int a[max][max] = {{0,6,4,5,inf,inf,inf,inf,inf},
    	                   {inf,0,inf,inf,1,inf,inf,inf,inf},
    					   {inf,inf,0,inf,1,inf,inf,inf,inf},
    					   {inf,inf,inf,0,inf,inf,inf,2,inf},
    					   {inf,inf,inf,inf,0,9,7,inf,inf},
    					   {inf,inf,inf,inf,inf,0,inf,inf,2},
    					   {inf,inf,inf,inf,inf,inf,0,inf,4},
    					   {inf,inf,inf,inf,inf,inf,inf,0,4},
    					   {inf,inf,inf,inf,inf,inf,inf,inf,0}};
    	int n= 9;
    	int e= 11;
    	createadj(b,a,n,e);
    	showadj(b);
    	printf("\n拓扑排序输出序列为: "); 
    	aoesearch(b,ky,d);
    	printf("\n ");
    	printf("\n关键活动如下:\n");
    	showpath(b,ky,d);
    	return 0;
    }
    
    

    程序运行如下:
    在这里插入图片描述

    展开全文
  • AOE网络-关键路径

    万次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。先回顾下拓扑排序中讲到的AOV网络,AOV网络即“Activity On Vertex”,即图上每一个顶点表示的是一个事件或者说一个活动,而顶点...

    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。先回顾下拓扑排序中讲到的AOV网络,AOV网络即“Activity On Vertex”,即图上每一个顶点表示的是一个事件或者说一个活动,而顶点之间的有向边则表示这两个活动发生的先后顺序。

    在关键路径这个问题中,AOE网络指的是“Activity On Edge”,即图上的每一条边表示的是一个活动,顶点作为各个“入度边事件”的汇集点,意思是,某个顶点,当所有的“入度边事件”的活动全部完成后,才开始进行该顶点的“出度边事件”。在AOE网络中只有一个入度为零的点,称作源头顶点,和一个出度为零的目的顶点。AOE网络通常用来安排一些项目的工序。

    上图表示的就是AOE网络中的,有向边上方表示该活动的持续时间,也就是完成该活动要多长时间,有向边下方表示该活动的机动时间,机动时间是什么呢,下面等拿例子来讲解时再解释。顶点里又分为三部分,一部分是存放顶点的编号,另外两部分分别存放活动的最早完成时间(即到达该点用时最短),和最晚完成时间(即到达该点用时最长)。

    下面根据一个具体的例子来看到底什么是AOE网络和关键路径:

    在下面的有向无环图中,V1是源头顶点(即开始点),到V10结束,每一条边代表一个活动,有向边的方向表示活动完成后到达哪一个汇集点。有向边上方表示的是活动完成所需要的时间(也是持续时间)。假设活动a7和a8想要开始,那么必须等到活动a4和a5都完成后,a7和a8才能开始。

    还有一种更复杂的情况是:如果活动a7和a8要开始,必须要等活动a4、a5和a6都完成后,才能开始a7和a8活动(因为在AOE网络中有些活动是可以并行地进行的)。这样的情况怎么办?我们不可以把V5和V6顶点连接起来,为什么?因为我们看a9这个活动,它的开始与否和活动a4,a5均无关系,活动a9只需等待活动a6完成他就可以开始了,所以如果我们把V5和V6顶点连接起来,是不行的。那要怎么办?方法是用一个无向虚线(标记线)把V5和V6连接,边上的权值设为0,如图:

    接着根据这个有向无环图,我们看看从开始到结束整个工程活动需要的最短时间是多少?答案是从开始点出发到完成点的最长路径的长度(这里的最长路径长度指的是路径上各个活动持续时间之和,不是指路径上边的数目)。从开始点到结束点的最长路径就叫做关键路径。从开始结点V1开始,它的最早完成时间自然是0了,然后到V2结点,V2结点的最早完成时间是5,同理V3结点最早需要4天完成,V4结点最早需要6天完成。

    接着到下一组,从V4到V6顶点,活动a6需要7天,所以V6上填上6+7=13,也就是说到达V6需要最早完成时间是13天。对于V5这个顶点,它的完成时间有三个,分别是5+3=8,4+2=6和13+0=13。这里我们就要选一个最大的填进去,因为V5的“出度边事件”要进行,也就是活动a7和a8要开始的话,必须等齐a4,a5和a6三个活动结束后才能开始,所以在a4、a5和a6中选一个完成时间最大的,就能确保三个活动都能完成。

    到这里我们就知道程序大概要怎么写了:

    首先我们需要一个Earliest[ ]数组来存放每一个顶点的最早完成时间,Earliest[ 1 ]=0代表的就是开始结点V1的最早完成时间是0,对于图中每一个顶点对<i, j>,Earliest[ j ]的值也就是j结点的最早完成时间就等于Earliest[ i ]+C<i, j>(也就是前一个结点i的最早完成时间加上i和j之间的有向边的权值),当结点j的入度边不止一条的时候,Earliest[ j ]存放的就是所有入度边中最大的值。

    按照这个思路,我们可以把图里接下来的顶点的完成时间都填好:

    到最后V10结束结点等于29,也就是说整个图的所有活动的最短完成时间是29天。

    最后到来看看这个图中活动的机动时间,什么是机动时间呢,就是指图中这些活动中,有哪些活动是一直进行下去的,没有休息时间的。例如活动a10需要3天完成,而获得a11需要2天,则a11有1天的休息时间等待a10完成,a11的这一天休息时间就是所谓的“机动时间”。

    我们用e(i)来表示活动ai的最早完成时间,l(i)表示ai的最迟开始时间,机动时间要怎么算呢?看图来说,我们从结束结点开始倒推,在保证整个工期都不推迟的情况下,也就是第29天开始,反推回去,看结点V9,活动a12需要5天,就是说在保证整个工期能在29天完成的情况下,V9的最晚开始时间(也就是最迟完成时间)是29-5=24,就是说活动a12最迟必须在第24天就要开始工作了。V7结点和V8结点同理,V7结点最迟必须在第24-3=21天就开始工作,V8结点最迟必须在第24-2=22天开始就工作。

    接着看V5结点,从V8倒推到V5,就是22-7=15,a8活动最迟第15天就要开始工作。而从V7倒推到V5的话,21-8=13,a8活动最迟第13天就要开始工作,这里出现两个不同的值,怎么选?答案是选最小值13,因为如果选择第15天开工,那么对于活动a7来说,就延迟了两天开工了,这样就不能保证后面能在29天内完成整个工程,所以遇到两种不同的最晚开始时间时,我们要选最小的,这样才能保证整个工期不被延误。

    同样的,看V6结点,从V8结点倒推到V6结点,22-5=17天,也就是活动a9的最迟开始时间可以是在第17天时才开工?答案是不行的,因为V6结点和V5结点有个虚线连着呢,V6结点,也就是活动a9的最迟开始时间同样是13天。

    从这里就可以看出我们的求机动时间的倒推时的推断是,需要一个Latest[ ]数组存放每一个结点的最迟开始时间,一开始初始化结束结点的Latest[ 10 ]=Earliest[ 1 ],也就是29。然后倒推时,Latest[ i ]就等于Last[ j ]-C<i, j>.。如果某个结点有多个出度边,那么就选择最小值赋给Last[ i ]就可以了。

    按照这个推断,就可以把剩下的顶点的最晚开始时间都算出来:

    V1顶点有三种选择,V2到V1等于5,V3到V1等于7,V4到V1等于0,因为我们要选择最小值,所以V1填上0。

    最后来看看每个结点的机动时间,我们从头开始看,活动a1需要工作5天才完成,到达V2结点中,最迟开始时间是10,也就是说活动a4最迟在第10天开始工作都不会耽误整个工期,而a1从第0天开始只需工作5天就能完成,所以活动a1的机动时间就是10-0-5=5,五天。活动a2最迟在第11天开始工作就可以了,而活动a2只需要4天就可以完成,所以a2的机动时间是11-0-4=7,七天。活动a3等于6-0-6=0,所以活动a3机动时间等于0,也就是说活动a3完成后就要开始下一个活动了,中间没有“休息时间”。

    同理可看出,a4的机动时间是13-5-3=5。a5的机动时间是13-4-2=9。a6是13-6-7=0。这样我们就可以把所有的机动时间都算出来:

    我们假设用e(i)表示活动ai的最早开始时间,用l(i)表示活动的最迟开始时间,那么两者之差l(i)-e(i)表示活动ai的机动时间,把e(i)=l(i)的活动我们称为“关键活动”。关键路径上所有的活动都是关键活动。回到关键路径的问题,关键路径有可能不止一条。所以找出关键路径即找出路径上所有活动都是关键活动的路径即可。

    /*拓扑排序*/
    bool TopSort(ListGraphNode MyGraph, Vertex TopOrder[]) 
    {
    	/*TopOrder[]数组用来顺序存储排序后的顶点的下标*/
    	/*在拓扑排序完成后直接顺序输出TopOrder[]里的元*/
    	/*素就能得到拓扑排序序列*/ 
    	int i;
    	int Indegree[MaxVertex], cnt;/*Indegree数组是图中顶点的入度,cnt是计数器*/
    	Vertex V;/*扫描V顶点的邻接点*/
    	PtrlPointNode W; /*邻接表方式表示图*/
    	Queue PtrQ=Start();
    	for (i=0; i<MaxVertex; i++) {
    		PtrQ->Data[i]=-1;
    	}
    	
    	/*初始化入度数组*/
    	for (V=0; V<MyGraph->numv; V++) {
    		Indegree[V]=0;
    	}
    	
    	/*遍历图,得到图中入各顶点的入度情况并存入Indegree数组中*/
    	for (V=0; V<MyGraph->numv; V++) {
    		for (W=MyGraph->PL[V].HeadEdge; W; W=W->Next) {
    			Indegree[W->Tail]++;
    		}
    	}
    	
    	/*将所有入度为0的顶点入列*/
    	for (V=0; V<MyGraph->numv; V++) {
    		if (Indegree[V]==0) {
    			Push(PtrQ, V);
    		}
    	}
    	
    	/*开始拓扑排序*/
    	cnt=0; /*初始化计数器为0*/
    	while (PtrQ->End!=PtrQ->Head) {
    		V=Delete(PtrQ);/*出列一个入度为0的顶点*/
    		TopOrder[cnt++]=V;/*拓扑排序数组里记录该出列顶点的下标*/
    		/*遍历对于V的每个邻接点W->PL.HeadEdge.index*/ 
    		for (W=MyGraph->PL[V].HeadEdge; W; W=W->Next) {
    			/*若删除V能使该顶点的入度为0*/
    			if (--Indegree[W->Tail]==0) {
    				/*把该顶点入列*/
    				Push(PtrQ, W->Tail);
    			}
    			/*同时更新Earliest数组的值*/
    			if ((Earliest[V]+W->Weight)>Earliest[W->Head]) {
    				Earliest[W->Tail]=Earliest[V]+W->Weight;
    			} 
    		}
    	}
    	/*最后判断*/
    	if (cnt!=MyGraph->numv) {
    		return false;/*说明该图里有回路,返回false*/
    	} else {
    		return true;
    	}
    }

    在拓扑排序过程中,我们就同时更新Earliest数组,把每一个顶点的最早完成时间填入到数组中。

    /*关键路径*/
    bool CriticalPath(ListGraphNode MyGraph, int TopOrder[])
    {
    	int k, ee, el;
    	PtrlPointNode W;
    	Queue List=Start();
    	/*得到后面逆序用*/
    
    	for (k=0; k<MyGraph->numv ; k++) {
    		Push(List, TopOrder[k]); 
    	} 
    
    	/*初始化Lastest数组*/ 
    	for (k=0; k<MyGraph->numv; k++) {
    		Lastest[k]=Earliest[MyGraph->numv-1];
    	}
    	
    	/*开始关键路径*/
    	while (List->End!=List->Head) {
    		k=Delete(List);/*出列一个入度为0的顶点*/
    		/*遍历对于V的每个邻接点W->PL.HeadEdge.index*/ 
    		for (W=MyGraph->PL[k].HeadEdge; W; W=W->Next) {
    		if (Lastest[k]>(Lastest[W->Tail]-W->Weight)) {
    			Lastest[k]=Lastest[W->Tail]-W->Weight;
    		}	
    	}
    	
    	//printf("关键路径为:"); 
    	for (k=0; k<MyGraph->numv; k++) {
    		W=MyGraph->PL[k].HeadEdge;
    		while (W) {
    			ee=Earliest[k];
    			el=Lastest[W->Tail]-W->Weight;
    			if (ee==el) {
    				/*两值相等说明它们是关键活动*/
    				printf("v%d--v%d=%d", MyGraph->PL[k].HeadEdge->Tail, MyGraph->PL[W->Head].HeadEdge->Tail, W->Weight);
    				}
    				W=W->Next;
    			} 
    		}
    	}
    }

    在关键路径的计算过程中再逆序计算出最迟开始时间即可。

    完整代码在个人代码云:

    https://gitee.com/justinzeng/codes/9jbqdrhgn8xl31y6vsw2u75

    展开全文
  • 一、关键路径 (一)AOE网 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为⽤边表示活动的网络,简称AOE网 (Activity On Edge NetWork) 在...

    一、关键路径

    (一)AOE网

    • 在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为⽤边表示活动的网络,简称AOE网 (Activity On Edge NetWork)
      在这里插入图片描述
    • AOE⽹具有以下两个性质:
      ① 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;
      ② 只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发⽣。
      另外,有些活动是可以并行进行的

    在这里插入图片描述

    • 在AOE网中仅有⼀个入度为0的顶点,称为开始顶点(源点),它表示整个⼯程的开始;
    • 仅有⼀个出度为0的顶点,称为结束顶点(汇点),它表示整个⼯程的结束。

    (二)关键路径

    在这里插入图片描述

    • 从源点到汇点的有向路径可能有多条,所有路径中,具有最⼤路径⻓度的路径称为关键路径,⽽把关键路径上的活动称为关键活动
    • 完成整个⼯程的最短时间就是关键路径的⻓度,若关键活动不能按时完成,则整个⼯程的完成时间就会延⻓
      在这里插入图片描述
      在这里插入图片描述
    • 活动ai的时间余量d(i)=l(i)-e(i),表⽰在不增加完成整个⼯程所需总时间的情况下,活动ai可以拖延的时间
    • 若⼀个活动的时间余量为零,则说明该活动必须要如期完成,d(i)=0即l(i) = e(i)的活动ai是关键活动关键活动组成的路径就是关键路径

    (三)求关键路径的步骤

    在这里插入图片描述

    (四)求所有事件的最早发生时间

    1. 求所有事件的最早发生时间ve()

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    (五)求所有事件的最迟发⽣时间

    1. 求所有事件的最迟发⽣时间 vl()

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    (六)求所有活动的最早发生时间

    1. 求所有活动的最早发生时间e()

    在这里插入图片描述

    (七)求所有活动的最迟发生时间

    1. 求所有活动的最迟发生时间l()

    在这里插入图片描述

    (八)求所有活动的时间余量

    在这里插入图片描述

    (九)关键活动、关键路径的特性

    在这里插入图片描述
    在这里插入图片描述

    • 若关键活动耗时增加,则整个工程的工期将增长
    • 缩短关键活动的时间,可以缩短整个工程的工期
    • 当缩短到一定程度时,关键活动可能会变成非关键活动
      在这里插入图片描述
    • 可能有多条关键路径,只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的。
    展开全文
  • 代码实现 路径长度 与关键路径相关的需求有很多,不妨先拟定一个需求,仅关键路径的长度: 给定一张有向有权无环的AOE网络出其源点到汇点的关键路径长度 输入格式: 第一行包含两个整数n,m,表示顶点的个数...

    前言

    数据结构,一门数据处理的艺术,精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美,在为信息技术打下坚实地基的同时,也令无数开发者和探索者为之着迷。

    也因如此,它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持,我打算将这门课的笔记也写作系列博文,既用于整理、消化,也用于同各位交流、展示数据结构的美。

    此系列文章,将会分成两条主线,一条“数据结构基础”,一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主,“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

    欢迎关注博主,一起交流、学习、进步,往期的文章将会放在文末。


    话说在前面的章节,我们介绍了一种工程上常用的AOV网络,他可以清晰的表示工程中每项活动的先后顺序,并计算出满足要求的活动规划,也就是拓扑排序。

    这一节,我们将继续研究这类网络。

    AOE网络

    在一般工程项目中,我们不仅会关心每项活动的先后次序,更会关心活动之间更加严格的时间约束关系

    不妨改造AOV网络的有向无环图,在此基础上引入边权,使其成为有向有权无环图。

    以一条有向边代替一个活动,边权为其进行的时间长度,边的起点表示该任务的开始,终点表示该任务的完成。从点的角度来看,出边表示一个活动开始的状态,也称为一个事件,入边表示一个任务的完成。

    这样的图被称作AOE网络( A c t i v i t y   O n   E d g e   N e t w o r k Activity\ On\ Edge\ Network Activity On Edge Network)。如果比较他和AOV网络的名称,不难发现他将关注的重点从顶点变成了边,这也将是两个网络处理问题和算法不同之处的来源。

    在工程中由于一般只有一个起始点和一个完成点,所以在正常的情况下,一张AOE网络中也只有一个源点和汇点。其中源点入度为0,汇点出度为0。如下图:
    在这里插入图片描述

    在AOE网络中,我们关心的问题不在仅仅是任务进行的先后顺序,更包括了每个任务乃至整个工程项目的计划完成时间。一般来说,一些活动能够同时开工,他们会从同一顶点出发。有些状态必须等到若干前置工作的完成,这些任务会汇集到一个顶点处。

    画出工程对应的AOE网络可以使我们得出:

    • 完成整个工程至少需要多少时间
    • 为缩短完成工程所需要的时间,应当加快那些活动
    • 为了不延误整个工程,哪些活动不得延期,那些活动可以适当延期

    关键路径

    根据上文的叙述,不难发现整个工程完成的最短时间,取决于从源点到汇点的最长路径的长度。我们将这个路径定义为该网络的关键路径。上文图中的关键路径就如下所示:
    在这里插入图片描述
    在关键路径中的任何一环不能按时完成,就会延误整个项目的进度。如在上图中,标红的路径中任意一条路径的长度增加都会使得源点到汇点的最长路径增加。而增加其他边则不一定。

    需要注意的是,关键路径也有可能存在多条,定义中并没有限制一张AOE网络只能有一条关键路径。如将上图中的权值稍作修改,就会出现多条关键路径:
    在这里插入图片描述

    在关键路径上所有的活动都是关键活动。(需要注意的是在AOE网络中,活动是边而不是顶点)

    多条关键路径的来源往往就在于一些状态之间可能存在着不同的活动路径,他们的时间加和相同(就像上图中的状态15之间存在两条路径)。而不同的路径在经过相同的顶点时遵循着乘法原理(上图为 1 × 2 1\times2 1×2

    算法设计

    有了对关键路径的定义和分析,下面的重点就是如何从AOE网络中寻找关键路径。

    这里介绍一种基于拓扑排序的算法思路:

    1. 将源点加入队列,所有顶点默认最长距离为0
    2. 每次出队队首顶点,使用该顶点更新出边终点。若经过该边到达彼点的累计路径长度大于原有顶点距离,更新最长距离并记录当前顶点为其前驱
    3. 将该顶点“删除”(所有出边终点入度-1),如果有顶点入度为0,则加入队列
    4. 重复23过程,直至队列为空

    该算法基于拓扑排序算法,改进也并不大,只是在记录顶点的入度和出度之余多记录了源点到他的最长路径。

    代码实现

    路径长度

    与关键路径相关的需求有很多,不妨先拟定一个需求,仅求出关键路径的长度:

    给定一张有向有权无环的AOE网络,求出其源点到汇点的关键路径长度
    输入格式:
    第一行包含两个整数n,m,表示顶点的个数和边的条数
    接下来m行,每行3个整数表示每条边的起点,终点和权值

    存储格式采用邻接表,顶点信息定义如下:

    struct Edge{
    	int vertex;
    	Edge * next;
    	int len;
    	
    	Edge(int vertex,Edge * next){
    		this->vertex = vertex;
    		this->next = next;
    		this->len = len;
    	}
    };
    Edge *head[N];//边链表头结点数组
    int id[N];//入度
    int od[N];//出度
    int dis[N];//顶点到源点的最长距离
    

    代码实现如下:

    void link(int x,int y,int len){
    	Edge * edge = new Edge(y,head[x],len);
    	head[x] = edge; 
    }
    int queue[N];//队列
    int main(){
    	int n,m;
    	cin >> n >> m;
    	for(int i = 0,x,y,len;i < m;i++){//读入边
    		cin >> x >>y >>len;
    		od[x]++;
    		id[y]++;
    		link(x,y,len);
    	}
    	int l = 1,r = 0;//队列左右下标
    	for(int i = 1;i <= n;i++){
    		if(id[i] == 0){//入度为0的顶点入队
    			queue[++r] = i;
    		}
    	}
    	int k;
    	while(l <= r){//遍历队列,直至为空
    		k = queue[l++];
    		for(Edge * edge = head[k];edge != NULL;edge = edge->next){
    			id[edge->vertex]--;//删除边
    			if(id[edge->vertex] == 0){//如果后继节点入度为0,该节点入队
    				queue[++r] = edge->vertex;
    			}
    			if(dis[edge->vertex] < dis[k] + edge->len){//使用当前顶点更新相连顶点的最长距离
    				dis[edge->vertex] = dis[k] + edge->len;
    			}
    		}
    	}
    	cout << dis[queue[r]] << endl;//汇点一定在队列的最后,想想这是为什么?
    }
    

    编译执行程序,输入上面的示例图:
    在这里插入图片描述

    打印路径

    一个程序能找出关键路径长度往往是不够的,我们还需要得出关键路径上的关键活动。

    那么如果题目需求输出一条关键路径应该怎么处理呢?

    这个问题其实很好解决,我们在记录每条边的距离源点的最远距离的同时记录其最远路径上的前驱。完成算法后从汇点开始,便可以顺藤摸瓜的找到一条从源点到汇点的关键路径上的全部顶点。

    下面让我们来修改上面拟定的需求:

    给定一张有向有权无环的AOE网络,求出其源点到汇点的关键路径长度,并输出任意一条关键路径
    输入格式:
    第一行包含两个整数n,m,表示顶点的个数和边的条数
    接下来m行,每行3个整数表示每条边的起点,终点和权值

    图的存储结构与上文相同,现需要额外定义一个最长路径的前驱顶点数组:

    int pre[N];//到达该顶点的最长路径上的前驱结点
    

    算法代码实现如下:

    void print(int k){//递归打印一条路径,由于顶点编号从1开始,所以值为0表示没有前驱
    	if(k == 0){
    		return;
    	}
    	print(pre[k]);
    	cout << k << " ";
    }
    void link(int x,int y,int len){
    	Edge * edge = new Edge(y,head[x],len);
    	head[x] = edge; 
    }
    int queue[N];//队列
    int main(){
    	int n,m;
    	cin >> n >> m;
    	for(int i = 0,x,y,len;i < m;i++){//读入边
    		cin >> x >>y >>len;
    		od[x]++;
    		id[y]++;
    		link(x,y,len);
    	}
    	int l = 1,r = 0;//队列的左右下标
    	for(int i = 1;i <= n;i++){
    		if(id[i] == 0){//入度为0的顶点入队
    			queue[++r] = i;
    		}
    	}
    	int k;
    	while(l <= r){//循环遍历队列中的顶点直至队列为空
    		k = queue[l++];
    		for(Edge * edge = head[k];edge != NULL;edge = edge->next){
    			id[edge->vertex]--;//删除该边
    			if(id[edge->vertex] == 0){//如果后继节点入度为0,后继节点入队
    				queue[++r] = edge->vertex;
    			}
    			if(dis[edge->vertex] < dis[k] + edge->len){//使用当前结点更新后继节点最长路径值和前驱
    				dis[edge->vertex] = dis[k] + edge->len;
    				pre[edge->vertex] = k;
    			}
    		}
    	}
    	cout << dis[queue[r]] << endl;//汇点一定在队列的末尾,想想这是为什么?
    	print(queue[r]);//打印源点到汇点的路径
    }
    

    再执行上述代码:
    在这里插入图片描述

    打印所有路径

    当然,能打印一条路径可能还不够过瘾。

    那么如果需要我们打印所有路径应该怎么办呢?

    办法总是有的,就是得多掉几根头发
    ——哲茨海氏沃茨基硕德

    关键路径不唯一,上面方法不能够打印所有的原因在于一个顶点可能是多条关键路径的交汇顶点。换句话说,就是一个顶点可能有多个前驱,而前驱数组只能记录其中的一个。

    其实本来源点到汇点的关键路径就不像是前驱链表表示的那样是一条链,更像是一张图。

    所以问题的关键就在于如何能找到一个顶点的所有的前驱。

    方法其实也很简单,对于一个顶点 k k k来说,只要枚举所有指向它的顶点 i i i,并从中选出所有满足dis[k] = dis[i] + len[i][k]的顶点,他们就是 k k k的前驱。

    对于上图来说,
    在这里插入图片描述

    8号顶点的前驱中只有5号满足dis[8] = dis[5] + 8

    而5号顶点的两个前驱2和3都分别满足dis[5] = dis[2] + 1dis[5] = dis[3] + 3

    所以只要根据这个方式,就可以找到一个顶点在关键路径中的所有前驱,并依次进行递归。

    什么?你问我怎么找一个顶点的前驱?我们的边都是有向边,只能向后找不能向前找?
    在这里插入图片描述
    不过也不是没有解决办法,我们可以将所有的边都存储一个反向的边,并且在边结点中加上一个字段标记正边还是反边。在拓扑排序过程中只用正边,获取路径的过程中只用反边就好啦~
    在这里插入图片描述
    为此,我们需要修改邻接表结点的定义:

    struct Edge{
    	int vertex;
    	Edge * next;
    	int len;
    	bool dir;//true代表正向,false代表反向
    	
    	Edge(int vertex,Edge * next,int len,bool dir){
    		this->vertex = vertex;
    		this->next = next;
    		this->len = len;
    		this->dir = dir;
    	}
    };
    Edge * head[N];//边链表头结点数组
    
    int path[N];//递归打印路径辅助数组
    void print(int k,int cnt){//递归打印所有路径
    	path[cnt] = k;
    	if(dis[k] == 0){//如果该顶点为源点,打印路径
    		for(int i = cnt;i > 0;i--){
    			cout << path[i] << " ";
    		}
    		cout << endl;
    		return;
    	}
    	for(Edge * edge = head[k];edge != NULL;edge = edge->next){//遍历所有反边,找到关键路径上的前驱
    		if(edge->dir){
    			continue;
    		}
    		if(dis[k] == dis[edge->vertex] + edge->len){//找到关键路径上的前驱并递归打印
    			print(edge->vertex,cnt + 1);
    		}
    	} 
    }
    void link(int x,int y,int len,bool dir){
    	Edge * edge = new Edge(y,head[x],len,dir);
    	head[x] = edge; 
    }
    int queue[N];//队列
    int main(){
    	int n,m;
    	cin >> n >> m;
    	for(int i = 0,x,y,len;i < m;i++){//读入边
    		cin >> x >>y >>len;
    		od[x]++;
    		id[y]++;
    		//正反边都要建
    		link(x,y,len,true);
    		link(y,x,len,false);
    	}
    	int l = 1,r = 0;//队列的左右下标
    	for(int i = 1;i <= n;i++){
    		if(id[i] == 0){//入度为0的顶点入队
    			queue[++r] = i;
    		}
    	}
    	int k;
    	while(l <= r){//循环遍历队列中的顶点直至队列为空
    		k = queue[l++];
    		for(Edge * edge = head[k];edge != NULL;edge = edge->next){
    			if(edge->dir == false){
    				continue;
    			}
    			id[edge->vertex]--;//删除该边
    			if(id[edge->vertex] == 0){//如果后继节点入度为0,后继节点入队
    				queue[++r] = edge->vertex;
    			}
    			if(dis[edge->vertex] < dis[k] + edge->len){//使用当前结点更新后继节点最长路径值和前驱
    				dis[edge->vertex] = dis[k] + edge->len;
    			}
    		}
    	}
    	cout << dis[queue[r]] << endl;//汇点一定在队列的末尾,想想这是为什么?
    	print(queue[r],1);//打印源点到汇点的路径
    }
    

    执行示例,发现两条关键路径:
    在这里插入图片描述


    往期博客


    参考资料:

    • 《数据结构》(刘大有,杨博等编著)
    • 《算法导论》(托马斯·科尔曼等编著)
    • OI WiKi
    展开全文
  • 教你轻松计算AOE关键路径

    万次阅读 多人点赞 2018-09-19 16:14:23
    转:教你轻松计算AOE关键路径 认识AOE网  有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。  在AOV网的边上加上...
  • 在Windows7 64位+VS2015上运行求解AOE关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
  • 选择题快速求解AOE网的关键路径

    千次阅读 多人点赞 2020-11-28 12:12:26
    求解AOE关键路径时,书上的方法为先从源点到汇点求解事件最早发生时间ve,再从汇点到源点求解事件最迟发生时间vl,再利用ve和vl求解每个活动的最早开始时间e(i)和最迟开始时间l(i),e(i)和l(i)相等的活动则为关键...
  • AOE网络关键路径问题

    千次阅读 2017-06-04 12:01:31
    寻找AOE网络关键路径目的是:发现该活动网络中能够缩短工程时长的活动,缩短这些活动的时长,就可以缩短整个工程的时长。因此,寻找关键路径就是寻找关键活动。接下来开始寻找一个工程中的关键路径(关键活动)。...
  • 求AOE网络关键路径

    2012-07-09 02:54:44
    用C++实现的代码,求AOE网络关键路径,有详细注释
  • //求AOE网络中的关键路径算法 #include <cstdio> #include <cstring> #define MAXN 100 //顶点个数的最大值 #define MAXM 200 //边数的最大值 struct ArcNode { int to, dur, no; //边的另一个顶点持续时间活动序号 ...
  • AOE网络关键路径(一)

    万次阅读 2014-04-07 00:24:12
    1、与AOV网络密切相关的是AOE网络。如果在DAG中用有向边表示一个工程的各项活动,用有向边上的权值表示活动的持续时间,用顶点表示事件,则这种有向图叫做用边表示活动的网络(Activity On Edge),简称AOE网络; ...
  • AOE网上的关键路径

    千次阅读 2019-05-30 22:01:55
    AOE网上的关键路径 Time Limit:2000 ms Memory Limit:65536 KiB Problem Description ...
  • AOE网中,从源点到汇点最长的路径称为关键路径,在关键路径上的活动称为关键活动。 因为AOE网中的活动是可以并行进行的,所以整个工程的时间开销,其实是最长路径的时间开销。即关键路径制约整个工程的工期。 &...
  • 出所给的AOE−网的关键路径出所给的AOE-网的关键路径出所给的AOE−网的关键路径。 输入 若干行整数,第一行有2个数,分别为顶点数v和弧数a,接下来有a行,每一行有3个数,分别是该条弧所关联的两个顶点...
  • AOE网的关键路径

    2021-01-03 11:00:28
    目录引入AOE网的判断拓扑排序事件的最早发生时间和最晚发生时间活动的最早开始时间和最晚开始时间 引入 生活中往往有着这样的场景,我们想做一件事情,但是需要做其他的事情来达到这件事情,例如,学数据结构之前,...
  • AOE网求解关键路径完整代码

    千次阅读 2020-02-15 19:45:18
    泪奔,图终于看到最后啦~ AOE网手动实现比较复杂,学理论的时候也总是记不清(记过就忘),现在回头再看看代码,发现实现起来还是...3、e == l 判断是不是关键路径 这一部分强烈建议结合理论来看,理解AOE网模拟...
  • 1.计算每个活动的最早发生时间(正序) earliest[1]=0; earlest[k]=max{earliest[j],+dut[j][k]} 2.计算每个活动的最晚发生时间(逆序) lastest[n]=earliest[n];...lastest[j]=min{listest[k]-dut[j][k]}...将关键...
  • 参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 ... 1.关键路径 对整个工程和系统,人们关心的是两个方面的问题: 1)工程能否顺利进行 对AOV网进行拓扑排序 ... 对AOE求关键路径 ...
  • AOE(Activity On Edge)网:顾名思义,用边表示活动的网,当然它也是DAG。与AOV不同,活动都表示在了边上,如下图所示: 如上所示,共有11项活动(11条边),9个事件(9个顶点)。整个工程只有一个...
  • 利用AOE网求解关键路径问题

    千次阅读 2017-05-08 19:20:37
    利用AOE网求解关键路径问题,输出一个工程的所有关键活动。
  • 1.先对每个事件–顶点i(i=a1,a2···an)的最早发生时间 ve(i)=a1到ai的最长路径 2.每个事件–顶点i的最迟发生时间 vl(i)=每个顶点i的所有的*出边所对应的顶点k的ve(k)减去这个顶点k对应的出边的路径长度*的...
  • AOE网与关键路径 在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动持续的时间,称这样的有向图为边表示活动的网,简称 AOE网(activity on edge network)。AOE网中没有入边的...
  • 【笔记】AOE网与关键路径

    万次阅读 多人点赞 2017-12-02 01:06:32
    AOE关键路径 求关键路径的算法实现
  • 代码如下: #include <iostream> #include <stack> #include <string> using namespace std; const int N = 10010; using vnodeType = int; typedef struct Node { int adj;...//..
  • AOE网络关键路径

    千次阅读 2018-08-25 23:00:20
    更加具体的知识点请取中国大学MOOC搜索浙大版数据结构,这里只给出了代码的实现。这个算法我没有找到比较好的实现,所以自己实现的有些复杂... AOE: 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和...
  • AOE网和关键路径

    千次阅读 2018-12-07 16:25:32
    AOE网 抽象地看,AOE网是一种无环的带权有向图,其中: 顶点表示事件,有向边表示活动,边上的权值通常表示活动的持续时间。 图中一个顶点表示的事件,也就是它的人边所表示的活动都已完成,它的出边所表示的活动...
  • 找代码废了很大的时间,有些代码存在问题,...#裘宗燕数据结构中的aoe网络代码"""topological sort of direct graph """class Graph: #basic graph class, using adjacent matrix ...
  • 关键路径 AOV网相对应的是AOE(Activity On Edge) ,是边表示活动的有向无环图,如下图所示。图中顶点表示事件(Event),每个事件表示在其前的所有活动已经完成,其后的活动可以开始;弧表示活动,弧上的权值表示...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,076
精华内容 430
关键字:

aoe网络求关键路径