关键路径-ag真人游戏

aoe网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为aoe网（activity on edge network）。

如下图所示：

aov网与aoe网的比较

下面是aov网

下面是aoe网

下面介绍几个名词解释：

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

所以可以知道：

此图的etv和ltv和ete和lte

如下图：

由此，可以做出他的邻接表，如下所示：

所以可以得出他的关键路径：

代码如下：

// 边表结点声明
typedef struct edgenode
{
	int adjvex;
	struct edgenode *next;
}edgenode;
// 顶点表结点声明
typedef struct vertexnode
{
	int in;			// 顶点入度
	int data;
	edgenode *firstedge;
}vertexnode, adjlist[maxvex];
typedef struct
{
	adjlist adjlist;
	int numvertexes, numedges;
}graphadjlist, *graphadjlist;
int *etv, *ltv;
int *stack2;			// 用于存储拓扑序列的栈
int top2;				// 用于stack2的栈顶指针
// 拓扑排序算法
// 若gl无回路，则输出拓扑排序序列并返回ok，否则返回error
status topologicalsort(graphadjlist gl)
{
	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 )
		{
			stack[  top] = i;	// 将度为0的顶点下标入栈
		}
	}
	
	// 初始化etv都为0
	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));
	
	while( 0 != top )
	{
		gettop = stack[top--];		// 出栈
		// printf("%d -> ", gl->adjlist[gettop].data); 
		stack2[  top2] = gettop;	// 保存拓扑序列顺序 c1 c2 c3 c4 .... c9
		count  ;				
		
		for( e=gl->adjlist[gettop].firstedge; e; e=e->next )
		{
			k = e->adjvex;
			// 注意：下边这个if条件是分析整个程序的要点！
			// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
			// 接着判断-1后入度是否为0，如果为0则也入栈
			if( !(--gl->adjlist[k].in) )	
			{
				stack[  top] = k;
			}
			
			if( (etv[gettop] e->weight) > etv[k] )
			{
				etv[k] = etv[gettop]   e->weight;
			}
		}
	}
	
	if( count < gl->numvertexes )	// 如果count小于顶点数，说明存在环
	{
		return error;
	}
	else
	{
		return ok;
	}
}
// 求关键路径，gl为有向图，输出gl的各项关键活动
void criticalpath(graphadjlist gl)
{
	edgenode *e;
	int i, gettop, k, j;
	int ete, lte;
	
	// 调用改进后的拓扑排序，求出etv和stack2的值
	topologicalsort(gl);
	
	// 初始化ltv都为汇点的时间
	ltv = (int *)malloc(gl->numvertexes*sizeof(int));
	for( i=0; i < gl->numvertexes; i   )
	{
		ltv[i] = etv[gl->numvertexes-1];
	}
	
	// 从汇点倒过来逐个计算ltv
	while( 0 != top2 )
	{
		gettop = stack2[top2--];	// 注意，第一个出栈是汇点
		for( e=gl->adjlist[gettop].firstedge; e; e=e->next )
		{
			k = e->adjvex;
			if( (ltv[k] - e->weight) < ltv[gettop] )
			{
				ltv[gettop] = ltv[k] - e->weight;
			}
		}
	}
	
	// 通过etv和ltv求ete和lte
	for( j=0; j < gl->numvertexes; j   )
	{
		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(" length: %d , ", gl->adjlist[j].data, gl->adjlist[k].data, e->weight );
			}
		}
	}
}