重要概念与基本思想
- AOE (Activity On Edges)网络 如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(Activity)，用边上的权值表示活动的持续时间(Duration)，用顶点表示事件(Event)，则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。AOE网是一个带权的有向无环图。
AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：
a、完成整个工程至少需要多少时间(假设网络中没有环)?
b、为缩短完成工程所需的时间, 应当加快哪些活动?
- AOE网的性质：
（1）只有某顶点所代表的事件发生后，从该顶点出发的各活动才能开始。
（2）只有进入某顶点的各活动都结束，该顶点所代表的事件才能发生。
- 关键路径(Critical Path) 在AOE网络中, 有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。
- 关键活动：关键路径上的活动称为关键活动。显然，关键活动的延期，会使整个工程延期，但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。
- 几个重要的标识符的含义（只有深刻理解这四个标识符的意义，才能解决灌浆路径问题）：
事件的最早发生时间Ve[k]：
Ve[k]是指从始点开始到顶点Vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。事件的最晚发生时间Vl[k]：
Vl[k]是指在不推迟整个工期的前提下，事件vk允许的最晚发生时间。活动的最早开始时间e[i]
若活动ai由弧<vk,vj>表示，则活动ai的最早开始时间应该等于事件vk的最早发生时间。因而，有：e[i]=ve[k]。活动的最晚开始时间l[i]
活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开始的最晚时间。ai由弧<vk,vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。 因而有：l[i]=vl[j]-len<vk,vj>。 - 几个重要的公式：
如果活动ai 由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系：
这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。也就是说，ve(j-1)必须在vj 的所在前驱的最早发生时间求得之后才能确定，而vl(j-1)则必须在vj 的所有后继的最迟发生时间求得之后才能确定。e[i] = ve[j]
l[i] = Vl[k] - dut(<i,k>)
如果e[i] = l[i] ，则表明该活动为关键活动。
算法的基本思想
程序代码
/* AOE网的关键路径问题C代码实现 */
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 15
typedef int VertexType;
typedef struct Edge {
VertexType begin;
VertexType end;
int weight;
}Edge;
typedef struct Graph {
VertexType *ver;
Edge *Edge;
int VertexNum;
int EdgeNum;
int *In;
}Graph;
//创建AOE网
void CreateGraph( Graph **g, int nver, int nedg )
{
int i, j;
(*g) = (Graph *)malloc(sizeof(Graph));
(*g)->VertexNum = nver;
(*g)->EdgeNum = nedg;
int EdgeNum = (*g)->EdgeNum;
int VertexNum= (*g)->VertexNum ;
(*g)->Edge = (Edge *)malloc(sizeof(Edge)*(EdgeNum+1));
(*g)->In = (int *)malloc(sizeof(int)*(VertexNum+1));
(*g)->ver = (int *)malloc(sizeof(int)*(VertexNum+1));
printf("请输入AOE网的顶点:\n");
for( i=1; i<=VertexNum; i++ ) //存储顶点
scanf("%d", &(*g)->ver[i]);
for( i=1; i<=VertexNum; i++ ) //顶点的入度数组初始化为0
(*g)->In[i] = 0;
printf("请输入AOE网的边的头、尾和权值:\n");
for( i=1; i<=EdgeNum; i++ ) {
printf("a%d: ", i);
scanf("%d %d %d", &((*g)->Edge[i].begin) , &((*g)->Edge[i].end) , &((*g)->Edge[i].weight) );
j = (*g)->Edge[i].end;
(*g)->In[j]++;
}
}
//关键路径查找函数
void FindCPath( Graph *g )
{
int VertexNum = g->VertexNum ;
int EdgeNum = g->EdgeNum ;
int end;
int TopIndex;
int *Top = (int *)malloc(sizeof(int)*(VertexNum+1)); //Top数组用来存储AOE网的拓扑序列的编号
int *ve = (int *)malloc(sizeof(int)*(VertexNum+1)); //ve[i]表示事件Vi的最早开始时间
int *vl = (int *)malloc(sizeof(int)*(VertexNum+1)); //vl[i]表示事件Vi的最迟开始时间
int *e = (int *)malloc(sizeof(int)*(VertexNum+1)); //e[i]表示活动ai的最早开始时间
int *l = (int *)malloc(sizeof(int)*(VertexNum+1)); //l[i]表示活动ai的最迟开始时间
int i, j, k;
for( i=1; i<=VertexNum; i++ )
for( j=1; j<=VertexNum; j++ )
if( 0 == g->In[j] ) {
g->In[j] = -1;
Top[i] = j;
for( k=1; k<=EdgeNum; k++ )
if( g->Edge[k].begin == g->ver[j] ) {
end = g->Edge[k].end;
g->In[end]--;
}
break;
}
//求ve[i]
for( i=1; i<=VertexNum; i++ ) //ve数组初始化
ve[i] = 0;
for( i=1; i<=VertexNum; i++ ) {
TopIndex = Top[i];
for( j=1; j<=EdgeNum; j++ )
if( (g->ver[TopIndex] == g->Edge[j].begin) && (ve[g->Edge[j].end] < ve[TopIndex] + g->Edge[j].weight) )
ve[g->Edge[j].end] = ve[TopIndex] + g->Edge[j].weight;
}
//求vl[i]
for( i=1; i<=VertexNum; i++ )
vl[i] = ve[VertexNum];
for( i=VertexNum; i>=1; i-- ) {
TopIndex = Top[i]; //用逆拓扑序列求vl
for( j=1; j<=EdgeNum; j++ )
if( (g->Edge[j].end == g->ver[TopIndex]) && (vl[g->Edge[j].begin] > vl[TopIndex] - g->Edge[j].weight) )
vl[g->Edge[j].begin] = vl[TopIndex] - g->Edge[j].weight;
}
//求e[i]
for( i=1; i<=EdgeNum; i++ )
e[i] = ve[g->Edge[i].begin];
//求l[i]
for( i=1; i<=EdgeNum; i++ )
l[i] = vl[g->Edge[i].end] - g->Edge[i].weight;
printf("该AOE网的关键活动为:\n");
for( i=1; i<=EdgeNum; i++ )
if( e[i] == l[i] )
printf("a%d ", i);
printf("\n");
}
int main()
{
Graph *g;
int VertexNum, EdgeNum;
printf("请输入要创建的AOE网的顶点数和边数:\n");
scanf("%d %d", &VertexNum, &EdgeNum);
CreateGraph( &g , VertexNum, EdgeNum);
FindCPath( g );
return 0;
}
测试数据以及测试结果
测试通过