最新AOE关键路径汇总Word文档格式.docx
《最新AOE关键路径汇总Word文档格式.docx》由会员分享，可在线阅读，更多相关《最新AOE关键路径汇总Word文档格式.docx（27页珍藏版）》请在冰点文库上搜索。
ve（i）=Max{ve（k）+wk,i}<
vk,vi>
∈T，1≤i≤n-1
其中，T是所有以vi为头的弧的集合，wk,i是弧<
的权值，即对应活动<
的持续时间。
（2）事件vi的最迟发生时间vl（i）
事件vi的发生不得延误vi的每一后继事件的最迟发生时间。
为了不拖延工期，vi的最迟发生时间不得迟于其后继事件vk的最迟发生时间减去活动<
vi,vk>
求出ve（i）后可根据逆拓扑顺序从汇点开始向源点递推，求出vl（i）。
vl（n-1）=ve（n-1）
vl（i）=Min{vl（k）－wi,k}<
vi，vk>
∈S，0≤i≤n-2
其中，S是所有以vi为尾的弧的集合，wi,k是弧<
的权值。
（3）活动ai=<
vj,vk>
的最早开始时间e（i）
只有事件vj发生了，活动ai才能开始。
所以，活动ai的最早开始时间等于事件vj的最早发生时间ve（j），即：
e（i）=ve（j）
（4）活动ai=<
的最晚开始时间l（i）
活动ai的开始时间需保证不延误事件vk的最迟发生时间。
所以活动ai的最迟开始时间l（i）等于事件vk的最迟发生时间vl（k）减去活动ai的持续时间wj,k，即：
l（i）=vl（k）－wj,k
显然，对于关键活动而言，e（i）=l（i）。
对于非关键活动，l（i）－e（i）的值是该工程的期限余量，在此范围内的适度延误不会影响整个工程的工期。
一个活动ai的最晚开始时间l（i）和最早开始时间e（i）的差值l（i）－e（i）是该活动完成的时间余量。
它是在不增加完成整个工程所需的总时间的情况下，活动ai可以拖延的时间。
当一活动的时间余量为零时，说明该活动必须如期完成，否则就会拖延整个工程的进度。
所以称l（i）－e（i）=0，即l（i）=e（i）时的ai是关键活动。
二、关键路径求解的过程
（1）输入e条弧<
j，k>
，建立AOE-网的存储结构。
（2）从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i]（1≤i≤n-1）。
如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；
否则执行步骤（3）。
（3）从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]（n—2≥i≥2）；
（4）根据各顶点的ve和vl值，求每条弧（活动）ai的最早开始时间e（i）和最迟开始时间l（i）。
（5）找出e（i）=l（i）的活动，则为关键活动。
由关键活动形成的由源点到汇点的每一条路径就是关键路径，关键路径有可能不止一条。
三、关键路径算法的实现
由于每个事件的最早发生时间ve（i）和vl（i）要在拓扑序列的基础上进行计算，所以关键路径算法的实现要基于拓扑排序算法，我们仍采用邻接表做有向图的存储结构。
算法的实现要引入以下辅助的数据结构：
（1）一维数组ve（i）：
事件vi的最早发生时间。
（2）一维数组vl（i）：
事件vi的最迟发生时间。
（3）一维数组topo（i）：
记录拓扑序列的顶点序号。
【算法思想】
（1）调用拓扑排序算法，使拓扑序列保存在topo中。
（2）将每个事件的最早发生时间ve（i）初始化为0，ve[i]=0。
（3）根据topo中的值，按从前向后的拓扑次序依次求每个事件的最早发生时间。
①取得拓扑序列中的顶点k，k=topo[i]；
②用指针p依次指向k的每个邻接顶点，取得每个邻接顶点的序号j=p->
adjvex，依次更新顶点j的最早发生时间ve[j]：
if（ve[j]<
ve[k]+p->
weight）ve[j]=ve[k]+p->
weight;
（4）将每个事件的最迟发生时间vl（i）初始化为汇点的最早发生时间，vl[i]=ve（n-1）。
（5）根据topo中的值，按从后向前的逆拓扑次序依次求每个事件的最迟发生时间vl[i]。
adjvex，依次更新顶点k的最迟发生时间：
if（vl[k]<
vl[j]－p->
weight）vl[k]=vl[j]－p->
（6）从源点开始，对于每个顶点i，用指针p依次指向i的每个邻接顶点，取得每个顶点的序号j=p->
adjvex，分别计算活动<
vi，vj>
的最早发生时间和最迟发生时间e和l。
e=ve[i]；
l=vl[j]－p->
如果e和l相等，则活动<
为关键活动，输出弧<
。
【算法6.13】
图的关键路径问题的算法之一AOE.CPP
/*2013年5月14日修改**图的关键路径问题的算法之一AOE.CPP*/
#include<
iostream.h>
#defineMAXVEX100
#defineTRUE1
#defineFALSE0
typedefcharVertexType[MAXVEX];
//存放顶点信息的字符串
typedefstructArcNode
{intadjvex;
//相邻顶点字段
floatweight;
structArcNode*nextarc;
//链字段
}ArcNode;
//边表中的结点
typedefstructVNode
{VertexTypedata;
//顶点信息
ArcNode*firstarc;
//边表头指针
}VNode,AdjList[MAXVEX];
//顶点表中的结点
typedefstruct
{AdjListvertices;
intvexnum,arcnum;
//图的顶点个数和弧的条数
}ALGraph;
/*求出图中所有顶点的入度，方法是搜索整个邻接表*/
voidFindInDegree（ALGraphG,intinDegree[]）
{inti;
ArcNode*p;
for（i=0;
i<
G.vexnum;
i++）inDegree[i]=0;
//顶点入度数组赋初值
i++）
{p=G.vertices[i].firstarc;
while（p）
{inDegree[p->
adjvex]++;
p=p->
nextarc;
}
}
intTopologicalSort（ALGraphG,int*topo）//拓扑排序算法
{ArcNode*p;
inti,j,k,count=0,top=-1;
intindegree[MAXVEX];
FindInDegree（G,indegree）;
//求出图中所有顶点的入度
i++）//堆栈初始化
if（indegree[i]==0）//将入度为零的顶点入栈
{indegree[i]=top;
top=i;
while（top!
=-1）//栈不为空
{j=top;
top=indegree[top];
//取出当前栈顶元素
topo[count++]=j;
//topo数组存放拓扑序列
p=G.vertices[j].firstarc;
/*取该元素边表中的第一个边结点，删除该结点,构造新的AOV网*/
while（p）//删除以该顶点为起点的边
{k=p->
adjvex;
indegree[k]--;
if（indegree[k]==0）//将新的入度为零的边入栈
{indegree[k]=top;
top=k;
if（count<
G.vexnum）//AOV网中存在回路
{cout<
<
"
Theaovnetworkhasacycle\n"
;
returnFALSE;
cout<
拓扑序列为：
"
i++）cout<
V"
topo[i]<
endl;
/*输出拓扑序列*/
returnTRUE;
voidinsert（ALGraph&
G,inta,intb,floatweight）
/*在表尾插入表结点*/
{ArcNode*p,*temp;
temp=newArcNode;
temp->
adjvex=b;
nextarc=NULL;
weight=weight;
p=G.vertices[a].firstarc;
if（p==NULL）
G.vertices[a].firstarc=temp;
else
{while（p->
nextarc!
=NULL）p=p->
//找表尾
p->
nextarc=temp;
intCriticalPath（ALGraphG）//G为有向网，输出G的各项关键活动。
{inti,k,j,n,topo[MAXVEX];
floatve[MAXVEX],vl[MAXVEX],e,l;
if（!
TopologicalSort（G,topo））returnFALSE;
//调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回FALSE
n=G.vexnum;
//n为顶点个数
n;
i++）ve[i]=0;
//初始化顶点事件的最早发生时间
/*----------按拓扑次序求每个事件的最早发生时间---------*/
{k=topo[i];
//取得拓扑序列中的顶点序号k
p=G.vertices[k].firstarc;
//p指向k的第一个邻接顶点
while（p!
=NULL）//依次更新k的所有邻接点的最早发生时间
{j=p->
//j为邻接顶点的序号
if（ve[j]<
weight）//更新顶点j的最早发生时间ve[j]
ve[j]=ve[k]+p->
//p指向k的下一个邻接顶点
}//while
}//for
i++）vl[i]=ve[n-1];
//初始化顶点事件的最迟发生时间
/*----------按逆拓扑次序求每个事件的最迟发生时间---------*/
for（i=n-1;
i>
=0;
i--）
//p指向k的第一个邻接顶点
=NULL）//依次更新k的所有邻接点的最迟发生时间
if（vl[k]>
vl[j]-p->
weight）//更新顶点k的最迟发生时间vl[k]
vl[k]=vl[j]-p->
/*----------判断每一活动是否为关键活动---------*/
i++）//每次循环针对vi为活动开始点的所有活动
//p指向i的第一个邻接顶点
=NULL）
//j为i的邻接顶点的序号
e=ve[i];
//计算活动<
的最早开始时间
l=vl[j]-p->
的最迟开始时间
if（e==l）cout<
G.vertices[i].data<
，"
G.vertices[j].data<
>
"
//p指向i的下一个邻接顶点
}//CriticalPath
voidmain（）//主函数
{ALGraphG={"
V0"
NULL,"
V1"
V2"
V3"
V4"
NULL,
V5"
V6"
V7"
V8"
NULL};
//顶点初始化
G.vexnum=9;
insert（G,0,1,6）;
insert（G,0,3,5）;
insert（G,0,2,4）;
insert（G,1,4,1）;
insert（G,2,4,1）;
insert（G,3,5,2）;
insert（G,4,6,9）;
insert（G,4,7,7）;
insert（G,5,7,4）;
insert（G,6,8,2）;
insert（G,7,8,4）;
if（CriticalPath（G）==FALSE）
Thereisnocriticalpath!
\n"
v0v2v3v5v1v4v7v6v8
v0，v1>
，<
v1，v4>
v4，v6>
v4，v7>
v6，v8>
v7，v8>
有两条关键路径：
（v0，v1，v4，v6，v8）和（v0，v1，v4，v7，v8）
图的关键路径问题的算法之二AOE.CPP
/*2013年4月29日修改**图的关键路径问题的算法AOE.CPP*/
/*存放顶点信息的字符串*/
typedeffloatAdjType;
/*相邻顶点字段*/
AdjTypeweight;
/*链字段*/
/*边表中的结点*/
/*顶点信息*/
/*边表头指针*/
/*顶点表中的结点*/
/*图的顶点个数*/
/*顶点入度数组赋初值*/
voidmakeNewAOV（ArcNode*p,int*indegree,int&
top）
{intk;
while（p）/*删除以该顶点为起点的边*/
if（indegree[k]==0）/*将新的入度为零的边入栈*/
inttopoSort（ALGraphG,int*topo）/*拓扑排序算法*/
inti,j,count=0,top=-1;
/*求出图中所有顶点的入度*/
if（indegree[i]==0）/*将入度为零的顶点入栈*/
=-1）/*栈不为空*/
/*取出当前栈顶元素*/
/*ptopo数组存放拓扑序列*/
makeNewAOV（p,indegree,top）;
/*对indegree数组进行修改*/
G.vexnum）/*AOV网中存在回路*/
topo[i]+1<
/*找表尾*/
voidmakeList（ALGraph&
G）/*邻接表的构造*/
i++）/*给顶点指针域赋初值*/
G.vertices[i].firstarc=NULL;
#defineMAXEDGE100/*MAXEDEG为边的最大数目*/
voidcountve（ALGraphG,int*topo,AdjType*ve）/*计算各事件的最早发生时间*/
{inti,j,k;
/*ee数组赋初值*/
for（k=0;
k<
k++）/*求事件vj可能的最早发生时间ee（j）*/
{i=topo[k];
//k仅起控制作用
p=G.vertices[i].firstarc;
if（ve[i]+p->
weight>
ve[j]）ve[j]=ve[i]+p->
voidcountvl（ALGraphG,int*topo,AdjType*ve,AdjType*vl）/*计算各事件的最迟发生时间*/
i++）/*求事件vi允许的最迟发生时间vl（i）*/
vl[i]=ve[G.vexnum-1];
/*每个事件的最迟发生时间赋初值为最生事件的最早发生时间
升级会员 