数据结构之关键路径

1、AOE网AOE网是⼀个带权的有向无环图其中顶点表示事件Event弧表示活动权表示活动持续的时间。2、源点和汇点AOE网中入度为零的点称为源点将出度为零的点称为汇点。3、关键路径完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径就叫做关键路径。ETVEarliest Time Of Vertex)事件最早发生时间就是顶点的最早发生时间。LTVLatest Time Of Vertex)事件最晚发生时间就是每个顶点对应的事件最晚需要开始的时间如果超出此时间将会延误整个工期。ETE(Earliest Time Of Edge)活动的最早开工时间就是弧的最早发⽣时间。LTE(Lastest Time of Edge)活动的最晚开工时间就是不推迟工期的最晚开工时间。4、关键路径算法关键路径Critical Path针对有向无环加权图AOE网工程活动网络是从源点入度为0到汇点出度为0的最长路径。路径上的活动称为关键活动关键路径长度决定整个工程的最短完成时间关键活动延时会直接导致整体工程延时。步骤1拓扑排序对AOE网进行拓扑排序得到有序节点序列若图存在环则无关键路径工程无法正常进行。步骤2计算最早发生时间 ve[]ve[i]节点i事件的最早发生时间从源点正向推导。公式源点 ve[start] 0遍历拓扑序列对当前节点u的所有出边 u→v权重w执行 ve[v] max(ve[v], ve[u] w)。步骤3计算最晚发生时间 vl[]vl[i]节点i事件的最晚发生时间不推迟整体工程工期从汇点逆向推导。公式汇点 vl[end] ve[end]逆序遍历拓扑序列对当前节点v的所有入边 u→v权重w执行 vl[u] min(vl[u], vl[v] - w)。步骤4筛选关键节点与关键路径若节点满足 ve[i] vl[i]该节点为关键节点由相邻关键节点组成的路径即为关键路径。#includeiostream#includevector#includequeue#includecstring#includealgorithmusingnamespacestd;constintMAXN105;constintINF0x3f3f3f3f;// 邻接表存储: to目标节点, weight边权, next下一条边structEdge{intto,w;Edge(intt,intww):to(t),w(ww){}};vectorEdgeadj[MAXN];// 正向邻接表(拓扑、求ve)vectorEdgereverseAdj[MAXN];// 逆向邻接表(求vl)intinDegree[MAXN];// 入度数组vectorinttopoSeq;// 存储拓扑排序序列intve[MAXN],vl[MAXN];// 最早、最晚发生时间// 拓扑排序booltopoSort(intn){queueintq;// 初始化入度为0的节点入队for(inti1;in;i){if(inDegree[i]0)q.push(i);}while(!q.empty()){intuq.front();q.pop();topoSeq.push_back(u);// 遍历出边更新后继节点入度for(Edge e:adj[u]){intve.to;inDegree[v]--;if(inDegree[v]0)q.push(v);}}// 拓扑序列长度不等于节点数说明有环无关键路径returntopoSeq.size()n;}// 计算关键路径voidcriticalPath(intn){// 1. 初始化ve数组正向求最早发生时间memset(ve,0,sizeof(ve));for(intu:topoSeq){for(Edge e:adj[u]){intve.to,we.w;if(ve[v]ve[u]w){ve[v]ve[u]w;}}}// 2. 初始化vl数组逆向求最晚发生时间intendNodetopoSeq.back();fill(vl,vln1,INF);vl[endNode]ve[endNode];// 逆序遍历拓扑序列for(intitopoSeq.size()-1;i0;i--){intvtopoSeq[i];for(Edge e:reverseAdj[v]){intue.to,we.w;if(vl[u]vl[v]-w){vl[u]vl[v]-w;}}}// 3. 输出关键节点和关键路径cout 关键路径计算结果 endl;cout工程最短总工期ve[endNode]endl;cout关键节点;for(inti1;in;i){if(ve[i]vl[i]){couti ;}}coutendl;cout关键活动(边)endl;for(intu1;un;u){// 筛选关键节点之间的边if(ve[u]!vl[u])continue;for(Edge e:adj[u]){intve.to,we.w;if(ve[v]vl[v]ve[v]ve[u]w){cout节点u - 节点v (工期:w)endl;}}}}intmain(){// 初始化memset(inDegree,0,sizeof(inDegree));intn,m;cout请输入节点数、边数;cinnm;// 构建正向、逆向邻接表for(inti0;im;i){intu,v,w;cout请输入第i1条边(起点 终点 权重);cinuvw;adj[u].emplace_back(v,w);reverseAdj[v].emplace_back(u,w);inDegree[v];}// 拓扑排序判环if(!topoSort(n)){cout图中存在环路无关键路径endl;return0;}// 计算并输出关键路径criticalPath(n);return0;}