有向无环图（DAG）中的最长路径问题

题目描述
给定一个带权有向无环图（DAG），每个边有一个实数权重（可能是正数、负数或零），要求找到图中任意两个顶点之间的最长路径（即路径上所有边权重之和最大的路径）。注意，由于图中可能存在负权边，但不能有环（否则最长路径可能无限大），因此问题在DAG上是有解的。

解题过程

1. 问题分析

   • 在一般图中，最长路径问题是NP难的，但DAG无环的特性允许我们使用动态规划高效求解。
   • 核心思路：利用拓扑排序确定顶点的处理顺序，确保计算到某个顶点时，其所有前驱顶点的最长路径已被计算完成。

2. 关键步骤

   • 拓扑排序：将DAG的所有顶点线性排列，使得对任意边(u→v)，u在排列中总出现在v之前。
   • 动态规划状态定义：设dist[v]表示从起点（或任意顶点）到顶点v的最长路径权重和。初始时，所有dist[v]设为负无穷（-∞），起点设为0（若固定起点）。
   • 状态转移：按拓扑顺序遍历顶点，对于每个顶点u，遍历其所有邻居v，更新dist[v] = max(dist[v], dist[u] + weight(u, v))。
   • 全局最长路径：若未指定起点和终点，需对每个顶点作为起点执行上述过程，或通过添加虚拟起点（连接所有顶点，边权为0）来统一计算。

3. 详细示例
   假设DAG如下（边权括号内）：
   A → B (3), A → C (2), B → D (5), C → D (1), C → E (4), D → E (2)

   • 拓扑排序结果：A, B, C, D, E（或A, C, B, D, E等）。
   • 以A为起点：
     • 初始化：dist[A]=0, 其他为-∞。
     • 处理A：更新B(0+3=3), C(0+2=2)。
     • 处理B：更新D(3+5=8)。
     • 处理C：更新D(max(8,2+1)=8), E(2+4=6)。
     • 处理D：更新E(max(6,8+2)=10)。
     • 最长路径A→B→D→E，权重和为10。

4. 算法复杂度

   • 拓扑排序时间复杂度O(V+E)。
   • 动态规划过程需遍历所有边，复杂度O(V+E)。
   • 总复杂度为O(V+E)，优于一般图的最长路径算法。

5. 应用场景

   • 项目管理中的关键路径分析（需将边权取反后求最短路径）。
   • 依赖调度中的最大完成时间计算。
   • 编译优化中的指令重排依赖分析。