有向无环图(DAG)中是否存在O(|E|)复杂度的最大瓶颈路径查找算法？

存在时间复杂度为O(|E|)的算法，可在有向无环图（DAG）上求解s到t的最大瓶颈容量路径。

最大瓶颈路径的定义为：s到t的所有路径中，路径边容量的最小值最大的那条路径。我们可以为每个节点u定义max_bottleneck[u]，表示从s到u的所有路径能达到的最大瓶颈值，通过动态规划的方式递推该值即可得到结果。

递推规则：对任意边u→v（边容量为c），通过u到达v的路径瓶颈为min(max_bottleneck[u], c)，取所有能到达v的路径的瓶颈最大值作为max_bottleneck[v]的最终值。

• 第一步：对输入的DAG执行拓扑排序，得到节点的线性序列，保证所有边u→v的u都排在v的前面，拓扑排序的时间复杂度为O(|V|+|E|)。
• 第二步：初始化max_bottleneck数组：起点s的max_bottleneck[s] = INF（无穷大，根据容量取值范围调整即可），其余所有节点的初始值为-1或负无穷。如果需要输出具体路径，同步初始化prev数组记录每个节点的前驱节点。
• 第三步：按照拓扑排序的顺序逐个遍历节点u：
  • 遍历u的所有出边u→v，当前边容量为c
  • 计算候选瓶颈值：candidate = min(max_bottleneck[u], c)
  • 如果candidate > max_bottleneck[v]，则更新max_bottleneck[v] = candidate，同时设置prev[v] = u
• 第四步：遍历完成后，max_bottleneck[t]就是s到t的最大瓶颈容量。如果该值仍为初始值，说明s到t无可达路径。如果需要输出具体路径，从t出发沿着prev指针回溯到s，再反转序列即可得到完整路径。

整个算法的时间复杂度为O(|V| + |E|)，对于存在s到t路径的有效DAG场景，节点数|V|的量级不会超过边数|E|，因此该算法的时间复杂度可等价为O(|E|)，符合要求。

注意：该算法仅适用于DAG场景，通用有向/无向图的最大瓶颈路径无法在O(|E|)时间内求解，需要使用二分+DFS、Dijkstra变种等算法，时间复杂度最低为O(|E| log |V|)。

举个简单的DAG示例：

• 节点：s、a、b、t
• 边：s→a（容量5）、s→b（容量3）、a→t（容量4）、b→t（容量6）
• 拓扑排序结果：s, a, b, t
• 计算过程：
  1. 初始化max_bottleneck[s] = INF，其余为0
  2. 遍历s：更新a的max_bottleneck为5，b的为3
  3. 遍历a：更新t的max_bottleneck为min(5,4)=4
  4. 遍历b：候选值为min(3,6)=3，小于当前t的4，不更新
• 最终结果：s到t的最大瓶颈为4，对应路径s→a→t，符合预期。

内容的提问来源于stack exchange，提问作者tinyline