数据结构 有向无环图关键路径问题

### 有向无环图中的关键路径算法实现 对于有向无环图(DAG)的关键路径计算，主要涉及两个方面：一是求解各节点的最早发生时间和最迟发生时间；二是基于这些时间来识别哪些活动属于关键路径。 #### AOV网与AOE网定义 - **AOV网络** (Activity On Vertex Network): 节点代表活动或任务, 边表示活动之间的依赖关系[^1]. - **AOE网络** (Activity On Edge Network): 边代表具体的活动, 权重为该活动所需的时间; 而节点则标志着某些特定事件的发生时刻——即当所有指向它的前置活动结束之后才能启动后续活动[^2]. #### 关键路径原理概述 在一个仅有一个起点和终点的DAG里，完成全部工作的最小耗时由从起始位置至终止位置之间最长的一条路径决定。这条拥有最大总权重值的路径便是所谓的“关键路径”，而位于此路径上的那些操作就构成了“关键活动”。任何延迟都会直接影响整体项目的进度安排. #### 计算方法描述 为了找到这样的关键路径，通常采用如下步骤： 1. 对于给定的一个DAG G=(V,E), 需要先执行一次拓扑排序得到线性序列v_1,v_2,...,v_n. 2. 初始化ve[]数组用于记录每个顶点作为某项工作开始最早的可能时机(earliest event time); vl[]用来保存对应最晚允许发生的期限(latest allowable occurrence). 3. 设置源结点s的ve[s]=0，并按照拓扑顺序依次更新其他节点u的ve[u], 公式为`ve[u] = max{ ve[v]+w(v,u) | v->u }`. 4. 反转上述过程设置vl[t]=ve[t](t为目标节点)，再逆序遍历调整其余节点u的vl[u], `vl[u] = min{ vl[w]-w(u,w) | u->w }`. 最后通过比较每一条弧e(i,j)两端所关联的时间差d[i][j]=vl[j]-ve[i]-weight(eij)，若等于零，则说明它是构成关键路径的一部分. ```python from collections import defaultdict, deque def find_critical_path(graph, weights): n = len(graph) indegree = [0]*n for i in range(n): for j in graph[i]: indegree[j] += 1 queue = deque([i for i in range(n) if indegree[i]==0]) # Step 1 & 2 Initialize earliest and latest times etime = [float('-inf')]*n ltime = [float('inf')]*n etime[0] = 0 while queue: node = queue.popleft() for neighbor in graph[node]: weight = weights[(node,neighbor)] new_time = etime[node] + weight if new_time > etime[neighbor]: etime[neighbor] = new_time indegree[neighbor] -= 1 if not indegree[neighbor]: queue.append(neighbor) ltime[-1] = etime[-1] visited = set() def dfs(node,time): nonlocal ltime if node in visited or ltime[node]<time: return False visited.add(node) result = True for prev_node in reversed(list(filter(lambda x:(x,node)in weights.keys(),range(len(indegree))))): edge_weight = weights[(prev_node,node)] next_time = ltime[node] - edge_weight if abs(next_time-(etime[prev_node]))<1e-9: critical_edges.append((prev_node,node)) elif dfs(prev_node,next_time)==False: continue else: ltime[prev_node] = min(ltime[prev_node],next_time) return True critical_edges = [] dfs(n-1,ltime[n-1]) return critical_edges ```