关键路径

什么是关键路径？

• 路径上各个活动所持续的时间之和成为路径长度
• 从源点到汇点具有最大的路径叫关键路径
• 在关键路径上的活动叫关键活动

各个工作画图如下

要在规定的时间内完成工作的话就需要算出关键路径总耗时

如上图所示，造发动机耗时为3，造外壳和造发动机可以同时进行，所以，关键路径是造发动机。然后不见集中到位，组装

代码实现

#include "stdio.h"
#include "stdlib.h"#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535typedef 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;elseG->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));//邻接序号为je->adjvex=j;e->weight=G.arc[i][j];//将当前顶点上的指向的结点指针赋值给ee->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;elsereturn 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(事件最晚发生时间) 出栈求ltvwhile (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;
}

 结果

Hello, 关键路径的求解!
TopologicSort:	0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 5 -> 7 -> 8 -> 9 -> 
etv:
etv[0] = 0 
etv[1] = 3 
etv[2] = 4 
etv[3] = 12 
etv[4] = 15 
etv[5] = 11 
etv[6] = 24 
etv[7] = 19 
etv[8] = 24 
etv[9] = 27 ltv:
ltv[0] = 0 
ltv[1] = 7 
ltv[2] = 4 
ltv[3] = 12 
ltv[4] = 15 
ltv[5] = 13 
ltv[6] = 25 
ltv[7] = 19 
ltv[8] = 24 
ltv[9] = 27 <0-2> length:4
<2-3> length:8
<3-4> length:3
<4-7> length:4
<7-8> length:5
<8-9> length:3
Program ended with exit code: 0