AOE网-关键路径

原创
2017/03/27 19:27
阅读数 28

AOV网中: 无环有向图中, 顶点表示活动 边表示先后顺序。

AOE网中:带权有向图中, 顶点表示事件,有向边表示活动,边上的权值表示活动的持续时间。

                     我们成为AOE网(Activity On Edge   Network)

AOE网中没有入边的顶点表示源点或始点,没有出边的叫终点或汇点。

AOE网要建立在活动之间制约关系没有矛盾的基础之上。

关键路径:我们把路径上各个活动持续时间之和称为路径长度,从源点到终点最大的长度为关键路径,在关键路径上的活动叫关键活动。

那么,显然对上图AOE网而言,所谓关键路径:

开始-->发动机完成-->部件集中到位-->组装完成。路径长度为5.5。我们只有在改变了关键路径的时间才有效。


AOE网表示工程流程图,具有工程特性,由于具有并行特性因此引入关键路径

1 只有在该顶点的事件发生后,从该顶点出发的活动才能进行。

2.只有进入到该顶点的所有活动完成后 该顶点事件才能执行。


对AOE网有待研究的问题是:

(1)完成整个工程至少需要多少时间?

(2)那些活动是影响工程进度的关键?

关键路径

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

整个工程完成的时间为从有向图的源点到汇点的最长路径

关键活动该弧上的权值增加 将使有向图上的最长路径的长度增加。关键活动的最早开始时间 =关键活动的最迟开始时间  意思是中间没有空闲时间干别的事了。

(1)事件的最早发生时间etv(earliest time of vertex): 即顶点Vk的最早发生时间。
(2)事件的最晚发生时间ltv(latest time of vertex): 即顶点Vk的最晚发生时间。
  也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。
(3)活动的最早开工时间ete(earliest time of edge): 即弧ak的最早发生时间。
(4)活动的最晚开工时间lte(latest time of edge): 即弧ak的最晚发生时间,也就是不推迟工期的最晚开工时间。关键还是求etv跟ltv数组。
然后根据最早开工时间ete[k]和最晚开工时间lte[k]相等判断ak是否是关键路径。



与拓扑序列邻接表结构不同的地方在于,弧链表增加了weight域,用来存储弧的权值。

求事件的最早发生时间etv的过程,就是从头至尾找拓扑序列的过程。

因此,在求关键路径之前,先要调用一次拓扑序列算法的代码来计算etv和拓扑序列表。

数组etv存储事件最早发生时间

数组ltv存储事件最迟发生时间


全局栈用来保存拓扑序列

//依据AOV网 求Topo图 来求 事件的最早发生时间etv数组
bool TopoSort(Gadjlist G)
{
	int count;//存储输出顶点的个数
	int top = 0;
	int* stack = new int[G.numV];//设立一个栈来存入度为0的数据
	for(int i=0;i<G.numV;i++)
	{
		if(G->adjlist[i].in == 0)
		{
			stack[top++] = i;//入栈
		}
	}
	int top2=0;//新加入的
	int *etv=new int[G.numV];//事件最早发生时间
	for(int i=0;i<G.numV;i++)
	{
		etv[i]=0;//初始化为0
	}
	stack2 = new int[G.numV];//初始化
	
	while(top != 0)
	{
		int gettop = stack[--top];//出栈
		stack2[top2++] = gettop;//新加入的  将弹出顶点序号压入拓扑序列栈中
		
		cout++;//统计输出顶点个数
		for(EdgeNode* e= G.adjlist[gettop].firstedge; e; e=e->next)
		{
			int k= e->adjvex;
			if(! (--G.adjlist[k].in))//将K号顶点的邻接点入度-1;
			{
				stack[top++] = k;
			}
			
			if(etv[gettop]+e->weight > etv[k])//新加入的
			{
				etv[k]=etv[gettop]+e->weight;
			}
		}
	}
	delete [] stack;
	if(cout<G.numV)
	{
		return false;//如果count<顶点数则说明存在环
	}
	else
	{
		return true;
	}
}

下面为关键路径算法代码

void CriticalPath(Gadjlist G)
{
	TopoSort(G);//求的事件最早发生时间 etv和stack2
	int* ltv = new int [G.numV];//事件最晚发生时间
	for(int i=0;i<G.numV;i++)
	{
		ltv[i]=etv[G.numV-1];//初始化事件最晚发生时间ltv,初始化为最大值
	}
	while(top2!=0)//top2是在TopoSort函数中求的的 所有点数=G.numV 
	{
		int gettop = stack[--top2];//拓扑序列出栈 后进先出
		for(EdgeNode* e=G.adjlist[gettop].firstedge;e;e=e->next)
		{
			int k=e->adjvex;
			if(ltv[k] - e->weight < ltv[gettop])
			{
				ltv[gettop] = ltv[k]-e->weight;
			}
		}
	}//经过while循环求出每顶点最晚发生时间
	for(int j=0;j<G.numV;j++)
	{
		for(EdgeNode* e=G.adjlist[j].firstedge;e;e=e->next)
		{
			int k= e->adjvex;
			int ete = etv[j];//活动最早时间
			int lte = ltv[k]-e->weight;//活动最晚时间
			if(ete == lte)
			{
				cout<<"<"<<cout<<G.adjlist[j].data<<cout<<","<<
				G.adjlist[k].data<<">"<<cout<<e->weight<<endl;;
			}
		}
	}
}


比如etv[1]=3而ltv[1]=7表示(如果单位按天计的话):
 哪怕V1这个事件在第7天才开始也是可以保证整个工程按期完成。
 你也可以提前V1时间开始,但是最早也只能在第3天开始。

该程序点时间复杂度O(V+E), 有时存在多条关键路径点有向无环图,这时如果想提高效率必须同时提高几条关键路径


本文同步分享在 博客“SoWhat1412”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部
返回顶部
顶部