图的应用——关键路径算法

关键路径

如果要对一个流程图获得最短时间,就必须要分析它们的拓扑关系,并找到当中最关键的流程,这个流程的时间就是最短时间。

在一个表示工程的带权有向图中,用顶点表示时间,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)。把AOE网中没有入边的顶点称之始点或源点,没有出边的顶点称为源点或汇点。由于一个工程,总有一个开始,一个结束,所以正常情况下AOE网只有一个源点一个汇点。如图所示。

图的应用——关键路径算法

既然AOE网是表示工程流程的,所以它就具有明显的工程的特性。如有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束,该顶点所代表的事件才能发生。

尽管AOE网与AOV网都是用来对工程建模的,但它们还是有很大的不同的,主要体现在AOV网是顶点表示活动的网,它只描述活动之间的制约关系,而AOE网是用边表示活动的网边上的权值表示活动持续的时间,如下图所示两图的对比。因此,AOE网是要建立在活动之间制约关系没有矛盾的基础之上,再来分析完成整个工程至少需要多少时间,或者为缩短完成工程所需时间’应当加快哪些活动等问题。

图的应用——关键路径算法

路径上各个活动所持续的时间之和称为路径长度,从源点到汇点且有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动。在上图中图的应用——关键路径算法就是关键路径,路径好穿那个地为5.5。

1.1 关键路径算法原理

关键路径算法需要定义几个参数:

  • 事件的最早发生时间etv(earliest time of vertex):即顶点的最早发生时间。
  • 事件的最晚发生时间ltv(latest time of vertex):即顶点的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间会延误整个工期。
  • 活动的最早开工时间ete(earliest time of edge):即弧的最早发生时间。
  • 活动的最晚开工时间lte(latest time of edge):即弧的最晚发生时间,也就是不推迟工期的最晚开工时间。

由1和2可以求得3和4,再根据ete[k]是否与lte[k]相等来判断顶点是否是关键活动。

1.2 关键路径算法

将AOE网转化成邻接表结构如图所示,注意与拓扑排序的不同的地方在于,弧链表增加了weight域,用来存储弧的权值。

图的应用——关键路径算法

只有缩短关键路径上关键活动的时间才可以减少整个工期长度。

只需要找到所有活动的最早开始时间和最晚开始时间,并且比较它们,如果相等就意味着此活动是关键活动,活动间的路径为关键路径。如果不等,则就不是。

关键路径算法的全局变量:

int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组 */
int *stack2; /* 用于存储拓扑序列的栈 */
int top2; /* 用于stack2的指针 */

关键路径算法的改进拓扑序列算法:

/* 拓扑排序 */
Status TopologicalSort(GraphAdjList GL)
{ /* 若GL无回路,则输出拓扑排序序列并返回1,若有回路返回0。 */
EdgeNode *e;
int i,k,gettop;
int top=0; /* 用于栈指针下标 */
int count=0;/* 用于统计输出顶点的个数 */
int *stack; /* 建栈将入度为0的顶点入栈 */
stack=(int *)malloc(GL->numVertexes * sizeof(int) );
for(i = 0; i<GL->numVertexes; i++)
if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */
stack[++top]=i;

top2=0;
etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /* 事件最早发生时间数组 */
for(i=0; i<GL->numVertexes; i++)
etv[i]=0; /* 初始化 */
stack2=(int *)malloc(GL->numVertexes * sizeof(int) );/* 初始化拓扑序列栈 */

printf("TopologicalSort:t");
while(top!=0)
{
gettop=stack[top--];
printf("%d -> ",GL->adjList[gettop].data);
count++; /* 输出i号顶点,并计数 */

stack2[++top2]=gettop; /* 将弹出的顶点序号压入拓扑序列的栈 */

for(e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k=e->adjvex;
if( !(--GL->adjList[k].in) ) /* 将i号顶点的邻接点的入度减1,如果减1后为0,则入栈 */
stack[++top]=k;

if((etv[gettop] + e->weight)>etv[k]) /* 求各顶点事件的最早发生时间etv值 */
etv[k] = etv[gettop] + e->weight;
}
}
printf("n");
if(count < GL->numVertexes)
return ERROR;
else
return OK;
}
/* 求关键路径,GL为有向网,输出G的各项关键活动 */
void CriticalPath(GraphAdjList GL)
{
EdgeNode *e;
int i,gettop,k,j;
int ete,lte; /* 声明活动最早发生时间和最迟发生时间变量 */
TopologicalSort(GL); /* 求拓扑序列,计算数组etv和stack2的值 */
ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* 事件最早发生时间数组 */
for(i=0; i<GL->numVertexes; i++)
ltv[i]=etv[GL->numVertexes-1]; /* 初始化 */

printf("etv:t");
for(i=0; i<GL->numVertexes; i++)
printf("%d -> ",etv[i]);
printf("n");

while(top2!=0) /* 出栈是求ltv */
{
gettop=stack2[top2--];
for(e = GL->adjList[gettop].firstedge; e; e = e->next) /* 求各顶点事件的最迟发生时间ltv值 */
{
k=e->adjvex;
if(ltv[k] - e->weight < ltv[gettop])
ltv[gettop] = ltv[k] - e->weight;
}
}

printf("ltv:t");
for(i=0; i<GL->numVertexes; i++)
printf("%d -> ",ltv[i]);
printf("n");

for(j=0; j<GL->numVertexes; j++) /* 求ete,lte和关键活动 */
{
for(e = GL->adjList[j].firstedge; e; e = e->next)
{
k=e->adjvex;
ete = etv[j]; /* 活动最早发生时间 */
lte = ltv[k] - e->weight; /* 活动最迟发生时间 */
if(ete == lte) /* 两者相等即在关键路径上 */
printf("<v%d - v%d> length: %d n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
}
}
}
发表评论

相关文章