首页 > 代码库 > AOE 网络
AOE 网络
1、定义
如果在无向环的带权有向图中
- 用有向边表示一个工程中的活动
- 用边上的权值表示活动的持续时间
- 用顶点表示事件
则这样的有向图叫做用边表示活动的网络,简称AOE网络
AOE在工程方面非常有用:
例如:
(1)完成整个工程至少需要多少时间(假设没有环);
(2)为缩短完成工程所需时间,应当加快那些活动?
从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同,完成不同路径的活动所需时间不同,但只有各条路径上所有活动都完成了,整个工程才完成。
Hence, 完成整个工程所需时间取决于从源点到汇点的最长路径长度,即在该路径上所有活动的持续时间之和,给路径称为关键路径。
为了找出关键路径,必须找出关键活动,即不按期完成就会影响整个工程完成的活动。
关键路径上的所有活动都是关键活动。
修改后的拓扑排序:
void TopologicalSort(AdjGraph G) { Stack S; StackEmpty(S); int j; for(int i=0;i<n;i++) //入度为0的顶点进栈 if(count[i]==0) Push(S,i); while(!StackEmpty(S)) { Pop(S,j); //退栈 cout << j << endl; //输出栈顶元素 Push(T,j); //j号顶点入栈 EdgeNode * p=data[j].firstarc; while(p!=NULL) //扫描出边表 { int k=p->adjvex; //另一顶点 if(--count[k]==0) //顶点入度减一 Psuh(S,k); //顶点入度减至0,进栈 if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info; p=p->nextarc; } } } CristicalPath(G) { vl[0..vexnum-1]=ve[vexnum-1]; while(!StackEmpty(T)) { Pop(T,j); p=G.data[j].firstarc; while(p!=NULL) { k=p->adjvex; dut=p->info; if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; } for(j=0;j<vexnum;j++) for(p=G.data[j].firstarc;p;p=p->next) { k=p->adjvex; dut=p->info; ee=ve[j]; el=vl[k]-dut; if(ee=el)printf("j,k"); } } }
算法分析:
在拓扑排序求Ve[i],与逆拓扑排序求Vl[i]时需要的时间复杂度为O(n+e),求各个活动e(k)与l(k)需要的时间复杂度为O(e),
则总的时间复杂度为O(n+e)
注意到并不是改变任何一个关键活动的时间都可以改变总时间
AOE 网络
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。