前言
在学习了最小路径的最小最短概念及拓扑排序的顶点先后顺序概念后，今天我们来了解另外一个图的应用----关键路径。通过关键路径的学习我们需要理解在实际生活中例如工程的每个步骤的时间点规划问题。
概念
例如，造一辆汽车，我们需要先制造各种各样的零件，然后组装成一辆完整的汽车。
那么在组装工作开始前，各部件得先制造出来，假如造一个轮子，需要0.5天时间，造一个发动机需要3天时间，早一个底盘需要2天时间，然后将各个部件集中到一起需要0.5天，组装好汽车需要2天时间，那么从开始制造到组装完成需要多长时间呢？
造汽车流程时间图
如上图所示，从开始到组装完成，因为制造零件是可通同时进行的，所以就看哪个零件花费时间最长，这样零件制造的最长时间就是哪个，也就是说
造发动机的3天时间最长，对总的时间影响最大，所以至少需要3+0.5+2 = 5.5天时间才能造好一辆车。从上例子可引出以下几个概念：
-
AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表表示活动的网。没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点，正常情况下，AOE网只有一个源点和一个汇点。 - 路径上各个活动持续的时间之和称为路径长度。
- 从开始点到结束点具有最大的路径叫
关键路径。 - 在关键路径上的活动叫做
关键活动。
例子
如下图所示例子，设计算法计算出源点到汇点的关键路径。
在计算之前，需要先了解求解过程中的几个核心参数：
-
事件最早发生时间etv（earliest time of vertex）：顶点Vk的最早发生时间。 -
事件最晚发生时间ltv（latest time of vertex）：顶点Vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出时间将会耽误整个工期。 -
活动的最早开工时间ete（earliest time of edge）：弧Ak的最早发生时间。 -
活动的最晚开工时间lte（latest time of edge）：弧Ak的最晚发生时间，也就是不推迟工期的最晚开工时间。
思路
求事件的最早发生时间etv（针对顶点）的过程，就是从头到尾去找拓扑序列的过程，所以求解关键路径之前，我们需要利用拓扑排序的思想去实现。
同样的关键路径的求解邻接表的方式更适合，初始化邻接表如下：
邻接表
演算过程
在最小路径等概念中我们是求最小路径，但是关键路径的求解求的是最大路径，比如造汽车图中的（开始-->造发动机-->部件集中-->组装完成 ）就是关键路径，因为用时最长，但是造发动机又是不得不走的路径。
求解etv（事件最早发生时间）
步骤一： 以V0源点开始，得到etv[1] = 3，即顶点V1事件的最早发生时间为V0-->V1的弧长3，同理etv[2] = 4，那么etv[3] = max(3+5,4+8) = 12，意思就是V3事件最早发生时间为12，可以理解为V3事件的开始需要满足V1和V2两个零件的完成，才能开始V3事件，所以V3需要等待V2更久，取两条路径中的最大值12。
可总结为以下规律：
- etv[0] = 0；
- etv[k] = mak { etv[i] + len<Vi, Vk> } , <Vi, Vk>属于图中弧集合中的一条。
步骤二：重复利用以上公式，计算得到如下etv数组：
etv
求解ltv（事件最晚发生时间）
事件最晚发生时间，在不耽误工期的情况下，比如上面造零件一样，造零件的最长时间内，各个零件时间安排是随机的，在最长时间造发动机3天时间内，可以第一个半天就把轮子造好，也可以在3天内的最后一个半天把轮子造好，只要不影响部件集中及后续工期，都是满足条件的。那么造轮子这个事件最晚发生时间就是2.5天的时候，再晚就会影响后续工期。
步骤一：因为etv[9]为图中最大路径27，所以汇点的最晚开始时间就是27，也就是到达汇点之前，必须经过27的权值。所以初始化ltv为etv最后一个事件的时间27。将源点到汇点的顶点序号依次入栈stack，从后往前开始比较计算。
步骤二：首次出栈的gettop = 9，但由于V9没有弧表，则没有相关的ltv更新。
步骤三：出栈gettop = 8，由于V8指向V9，ltv[9] = 27, ltv[8] = min(27, 27 - 3) = 24, V8-->V9弧长为3。更新ltv数组。
步骤四：出栈gettop = 7， 由于V7指向V8， ltv[8] = 24, ltv[7] = min(24, 24 - 5) = 19, 更新ltv数组。依次这么比较计算得到最终ltv结果如下：
ltv
演算公式如下：
- ltv[k] = etv[k] , 当 k = n-1 时；
- ltv[k] = min { ltv[i] - len<Vi,Vj> }，当 k < n - 1, <Vi,Vj>属于弧的集合。
ete（活动最早开工时间）& lte（活动最晚开工时间）
思路：
- 活动最早开工时间即弧Ak的最早发生时间。表示活动<Vk,Vj>的最早开工时间，是针对这条弧的说的，而这条弧的弧尾顶点Vk的事件发生了，它才可以发生，因为ete[k] = etv[k]。
- 活动最晚开工时间即弧<Vk,Vj>的最晚开工时间，但此活动再晚不能等Vj事件发生了才开始，而是必须在Vj事件之前发生，所以lte = ltv[j] - len<Vk, Vj>。
- 判断ete 与 lte 是否相等，相等就意味着活动之间没有任何空余时间，那么这条弧必定在关键路径中，此次活动称为关键活动，否则不是。
步骤一：着手V0顶点，指向V1， 所以ete = etv[0] = 0，lte = ltv[0] - 3 = 7 - 3 = 4, 判断ete != lte ,说明<V0, V1>不是关键活动。同时V0指向V2，所以ete = etv[0] = 0，lte = ltv[2] - 4 = 4 - 4 = 0, 判断ete == lte ,说明<V0, V2>是关键活动。
步骤二：继续来到V1顶点，先处理指向V4的弧，则ete = etv[1] = 3, lte = ltv[4] - 6 = 15 - 6 = 9，发现ete != lte， 说明<V1,V4> 不是关键活动。再处理指向的V3的弧，ete = etv[1] = 3, lte -= ltv[3] - 5 = 12 - 5 = 7, ete != lte ,说明<V1, V3>也不是关键活动。依此类推后续的弧，最终得到关键路径为下图中的绿色路径：
代码
#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/* 邻接矩阵结构 */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/* 邻接表结构****************** */
//边表结点
typedef struct EdgeNode
{
//邻接点域，存储该顶点对应的下标
int adjvex;
//用于存储权值，对于非网图可以不需要
int weight;
//链域，指向下一个邻接点
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;
/* **************************** */
/* 关于AOE网图的存储代码段-Begin */
//1.完成AOE网图关于邻接矩阵的存储
void CreateMGraph(MGraph *G)/* 构件图 */
{
int i, j;
/* printf("请输入边数和顶点数:"); */
G->numEdges=13;
G->numVertexes=10;
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=INFINITYC;
}
}
G->arc[0][1]=3;
G->arc[0][2]=4;
G->arc[1][3]=5;
G->arc[1][4]=6;
G->arc[2][3]=8;
G->arc[2][5]=7;
G->arc[3][4]=3;
G->arc[4][6]=9;
G->arc[4][7]=4;
G->arc[5][7]=6;
G->arc[6][9]=2;
G->arc[7][8]=5;
G->arc[8][9]=3;
}
//2.将邻近矩阵转化成邻接表
void CreateALGraph(MGraph G,GraphAdjList *GL){
int i,j;
EdgeNode *e;
*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
(*GL)->numVertexes=G.numVertexes;
(*GL)->numEdges=G.numEdges;
//读入顶点信息，建立顶点表
for(i= 0;i <G.numVertexes;i++)
{
(*GL)->adjList[i].in=0;
(*GL)->adjList[i].data=G.vexs[i];
//将边表置为空表
(*GL)->adjList[i].firstedge=NULL;
}
//建立边表
for(i=0;i<G.numVertexes;i++)
{
for(j=0;j<G.numVertexes;j++)
{
if (G.arc[i][j]!=0 && G.arc[i][j]<INFINITYC)
{
e=(EdgeNode *)malloc(sizeof(EdgeNode));
//邻接序号为j
e->adjvex=j;
e->weight=G.arc[i][j];
//将当前顶点上的指向的结点指针赋值给e
e->next=(*GL)->adjList[i].firstedge;
//将当前顶点的指针指向e
(*GL)->adjList[i].firstedge=e;
(*GL)->adjList[j].in++;
}
}
}
}
/* 关于AOE网图的存储代码段-End! */
int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组，全局变量 */
int *stack2; /* 用于存储拓扑序列的栈 */
int top2; /* 用于stack2的指针*/
//拓扑排序
Status TopologicalSort(GraphAdjList GL){
//若GL无回路,则输出拓扑排序序列且返回状态OK, 否则返回状态ERROR;
EdgeNode *e;
int i,k,gettop;
//栈指针下标;
int top = 0;
//用于统计输出的顶点个数.作为拓扑排序是否存在回路的判断依据;
int count = 0;
//建栈,将入度in = 0的顶点入栈;
int *stack = (int *)malloc(GL->numVertexes * sizeof(int));
//遍历顶点表上入度in �= 0 入栈
for (i = 0; i < GL->numVertexes;i++) {
//printf("%d %d\n",i,GL->adjList[i].in);
if ( 0 == GL->adjList[i].in ) {
stack[++top] = i;
}
}
//* stack2 的栈指针下标
top2 = 0;
//* 初始化拓扑序列栈
stack2 = (int *)malloc(sizeof(int) * GL->numVertexes);
//* 事件最早发生时间数组
etv = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));
//* 初始化etv 数组
for (i = 0 ; i < GL->numVertexes; i++) {
//初始化
etv[i] = 0;
}
printf("TopologicSort:\t");
while (top != 0) {
gettop = stack[top--];
printf("%d -> ", GL->adjList[gettop].data);
count++;
//将弹出的顶点序号压入拓扑排序的栈中;
stack2[++top2] = gettop;
//例如gettop为V0 ,那么与V0相连接的结点就有etv[1] = 3; etv[2] = 4;
//例如gettop为V1 ,那么与V1连接的结点就有etv[4]= 3+6=9; etv[3] = 8;
//例如gettop为V2 ,那么与V2连接的结点就有etv[5]= 4+7=11; etv[3] = 12;
//例如gettop为V3 ,那么与V3连接的结点就有etv[4]= 12+3=15;
for(e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k = e->adjvex;
//将i顶点连接的邻接顶点入度减1,如果入度减一后为0,则入栈
if(!(--GL->adjList[k].in))
stack[++top] = k;
//求各顶点事件的最早发生的时间etv值
//printf("etv[gettop]+e->weight = %d\n",etv[gettop]+e->weight);
//printf("etv[%d] = %d\n",k,etv[k]);
if ((etv[gettop] + e->weight) > etv[k]) {
etv[k] = etv[gettop] + e->weight;
}
}
}
printf("\n");
//打印etv(事件最早发生时间数组)
// for (i = 0; i < GL->numVertexes; i++) {
// printf("etv[%d] = %d\n",i,etv[i]);
// }
// printf("\n");
if(count < GL->numVertexes)
return ERROR;
else
return OK;
return OK;
}
//求关键路径, GL为有向网,则输出G的各项关键活动;
void CriticalPath(GraphAdjList GL){
EdgeNode *e;
int i,gettop,k,j;
//声明活动最早发生时间和最迟发生时间变量;
int ete,lte;
//求得拓扑序列,计算etv数组以及stack2的值
TopologicalSort(GL);
//打印etv数组(事件最早发生时间)
printf("etv:\n");
for(i = 0; i < GL->numVertexes; i++)
printf("etv[%d] = %d \n",i,etv[i]);
printf("\n");
//事件最晚发生时间数组
ltv = (int *)malloc(sizeof(int) * GL->numVertexes);
//初始化ltv数组
for (i = 0; i < GL->numVertexes; i++) {
//初始化ltv数组. 赋值etv最后一个事件的值
ltv[i] = etv[GL->numVertexes-1];
//printf("ltv[%d] = %d\n",i,ltv[i]);
}
//计算ltv(事件最晚发生时间) 出栈求ltv
while (top2 != 0) {
//出栈(栈顶元素)
gettop = stack2[top2--];
//找到与栈顶元素连接的顶点; 例如V0是与V1和V2连接
for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
//获取与gettop 相连接的顶点
k = e->adjvex;
//计算min(ltv[k]-e->weight,ltv[gettop])
if (ltv[k] - e->weight < ltv[gettop]) {
//更新ltv 数组
ltv[gettop] = ltv[k] - e->weight;
}
}
}
//打印ltv 数组
printf("ltv:\n");
for (i = 0 ; i < GL->numVertexes; i++) {
printf("ltv[%d] = %d \n",i,ltv[i]);
}
printf("\n");
//求解ete,lte 并且判断lte与ete 是否相等.相等则是关键活动;
//2层循环(遍历顶点表,边表)
for(j=0; j<GL->numVertexes;j++)
{
for (e = GL->adjList[j].firstedge; e; e = e->next) {
//获取与j连接的顶点;
k = e->adjvex;
//ete 就是表示活动 <Vk, Vj> 的最早开工时间, 是针对这条弧来说的.而这条弧的弧尾顶点Vk 的事件发生了, 它才可以发生. 因此ete = etv[k];
ete = etv[j];
//lte 表示活动<Vk, Vj> 的最晚开工时间, 但此活动再晚也不能等Vj 事件发生才开始,而是必须在Vj 事件之前发生. 所以lte = ltv[j] - len<Vk, Vj>.
lte = ltv[k]-e->weight;
//如果ete == lte 则输出j,k以及权值;
if (ete == lte) {
printf("<%d-%d> length:%d\n",GL->adjList[j].data, GL->adjList[k].data, e->weight);
}
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 关键路径的求解!\n");
MGraph G;
GraphAdjList GL;
CreateMGraph(&G);
CreateALGraph(G,&GL);
//拓扑排序
//TopologicalSort(GL);
//关键路径
CriticalPath(GL);
return 0;
}
网友评论