四、关键路径4.1 关键路径相关概念AOE网在一个表示工程的带权有向图中用顶点表示事件用有向边表示活动用边上的权值表示活动的持续时间这种有向图的边表示活动的网我们称之为AOE网Activity On Edge Network。我们把路径上各个活动所持续的时间之和称为路径长度从源点到汇点具有最大长度的路径叫关键路径在关键路径上的活动叫关键活动。4.2 关键路径代码实现int *etc,*ltv; // 事件最早发生时间和最迟发生时间数组 int *stack2; // 用于存储拓扑排序的栈 int top2; // 用于stack2的指针 // 拓扑排序 int TopologicalSort(GraphAdjList GL) { // 若GL无回路则输出拓扑排序并返回1若有则返回0 EdgeNode* e; int i,k,gettop; int top 0; int count 0; int *stack; stack (int*)malloc(GL-numVertexes* sizeof(int)); for (i 0; iGL-numVertexes;i) if (GL-adjList[i].in 0) stack[top] i; top2 0; etv (int*)malloc(GL-numVertexes*sizeof(int)); for (i 0;iGL-numVertexes;i) etv[i] 0; stack2 (int*)malloc(GL-numVertexes*sizeof(int)); while(top ! 0) { gettop stack[top--]; count; stack2[top2] gettop; for ( e GL-adjList[gettop].firstedge;e;e e-event) { k e-adjvec; 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) return ERROR; else return OK; }下面来看求关键路径的算法代码// 求关键路径GL为有向网输出G的各项关键活动 void CriticalPath(GraphAdjList GL) { EdegNode* e; int i,gettop,k,j; int ete,lte; TopologicalSort(GL); ltv (int*)malloc(GL-numVectexes*sizeof(int)); for (i 0;iGL-numVertexes;i) ltv[i] etv[GL-numVertexes-1]; while(top2 ! 0) { 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; } } for (j 0;jGL-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(v%d - v%d length: %d \n, GL-adjList[j].data,GL-adjList[k].data,e-weight); } } }