有向无环图（DAG）中单源最长路径问题的动态规划解法

题目描述

给定一个有向无环图（DAG），图中每条边都有一个权重（可以是正数、负数或零）。同时，给定图中的一个起点 s。问题是：从起点 s 出发，到图中其他每个顶点 v 的所有路径中，找出总权重最大的那条路径的权重值。这就是 DAG 上的单源最长路径问题。

注意：在一般的带权有向图中，如果存在正权重的环，那么最长路径可能是无限的（可以沿着正环无限走下去）。但在 DAG 中，由于不存在任何环，所以最长路径的权重是一个有限值。我们可以高效地解决这个问题。

解题过程

解决 DAG 上单源最长路径问题，核心思想是利用 DAG 的拓扑排序特性，结合动态规划（DP）进行递推计算。拓扑排序为顶点定义了一个线性顺序，保证在计算某个顶点 v 的最长路径时，所有可能到达 v 的顶点（即 v 的所有前驱）的最长路径都已经被计算出来。

第一步：理解问题与思路转化

1. 输入：一个有向无环图 G = (V, E)，一个起点 s ∈ V，以及一个边权重函数 w: E → R。
2. 输出：一个距离数组 dist[]，其中 dist[v] 表示从起点 s 到顶点 v 的最长路径的权重。如果从 s 无法到达 v，我们可以定义 dist[v] = -∞。
3. 思路：对于任意一个顶点 v，从 s 到 v 的最长路径，必然是通过 v 的某个直接前驱 u 过来的。也就是说，dist[v] = max_{(u, v) ∈ E} (dist[u] + w(u, v))。这里有一个初始条件：dist[s] = 0。这个递推关系是动态规划的状态转移方程。
4. 关键：要计算 dist[v]，我们必须先知道所有 u （存在边 u->v）的 dist[u] 值。这正是 DAG 的拓扑序能保证的：按照拓扑序处理顶点，当处理到顶点 v 时，所有指向 v 的顶点 u 在拓扑序中都排在 v 之前，因此它们的 dist 值已经被计算过了。

第二步：算法详细步骤

1. 拓扑排序：

   • 首先，对给定的 DAG 进行拓扑排序，得到一个顶点序列，记为 topo_order。
   • 拓扑排序可以通过 Kahn 算法（基于入度）或基于 DFS 的算法完成。这保证了对于序列中的任意一条有向边 (u, v)，u 都出现在 v 之前。

2. 初始化距离数组：

   • 创建一个大小为 |V| 的数组 dist，用于存储从起点 s 到每个顶点的最长路径权重。
   • 将 dist 的所有元素初始化为一个非常小的数，代表“负无穷”，表示“尚未可达”或“路径权重极小”。通常可以用 -inf 表示（在编程中可以用一个极小的数值，如 -10^9，或使用一个特殊标志）。
   • 设置 dist[s] = 0。这是我们的动态规划基础。

3. 按照拓扑序进行动态规划递推：

   • 按照拓扑排序 topo_order 的顺序，依次处理每个顶点 u。
   • 对于当前顶点 u，我们检查它的每一条出边 (u, v)。
   • 尝试用这条边去“松弛”（这里是“增大”，因为是求最长路径）目标顶点 v 的距离：
     • 新的可能距离是：dist[u] + w(u, v)。
     • 如果这个新值大于 v 当前记录的 dist[v]，我们就更新它：dist[v] = max(dist[v], dist[u] + w(u, v))。
   • 注意：如果 dist[u] 本身是“负无穷”（意味着 s 无法到达 u），那么通过 u 出发的任何边都无法有效更新后续顶点，可以跳过。

4. 处理结果：

   • 算法结束后，dist 数组中存储的就是从起点 s 到每个顶点的最长路径权重。
   • 对于所有从 s 不可达的顶点 v，dist[v] 将保持初始化的“负无穷”值。

第三步：算法示例

考虑以下 DAG，起点为 0。边上的数字代表权重。

顶点: 0, 1, 2, 3, 4, 5
边:
0 -> 1 (5)
0 -> 2 (3)
1 -> 2 (2)
1 -> 3 (6)
2 -> 4 (4)
2 -> 5 (2)
3 -> 5 (1)
4 -> 5 (2)

1. 拓扑排序：这个图的一个可能的拓扑排序是 [0, 1, 2, 3, 4, 5]。实际上，[0, 1, 3, 2, 4, 5] 也是一个有效的拓扑序。我们以 [0, 1, 2, 3, 4, 5] 为例。

2. 初始化：

   • dist = [-∞, -∞, -∞, -∞, -∞, -∞]
   • dist[0] = 0

3. 按拓扑序处理：

   • 处理顶点 0:
     • 边 0->1: dist[1] = max(-∞, 0+5) = 5
     • 边 0->2: dist[2] = max(-∞, 0+3) = 3
   • 处理顶点 1:
     • 边 1->2: dist[2] = max(3, 5+2) = 7 （更新！路径 0->1->2 比 0->2 更长）
     • 边 1->3: dist[3] = max(-∞, 5+6) = 11
   • 处理顶点 2:
     • 边 2->4: dist[4] = max(-∞, 7+4) = 11
     • 边 2->5: dist[5] = max(-∞, 7+2) = 9
   • 处理顶点 3:
     • 边 3->5: dist[5] = max(9, 11+1) = 12 （更新！路径 0->1->3->5 更长）
   • 处理顶点 4:
     • 边 4->5: dist[5] = max(12, 11+2) = 12 （没有更新）
   • 处理顶点 5:
     • 顶点 5 没有出边，无需处理。

4. 最终结果：

   • dist = [0, 5, 7, 11, 11, 12]
   • 解释：从 0 到 5 的最长路径是 0->1->3->5，权重为 5+6+1=12。

第四步：算法复杂度与特性

• 时间复杂度：O(V + E)。
  • 拓扑排序需要 O(V + E) 时间。
  • 动态规划递推需要遍历所有边一次，也是 O(V + E)。
  • 因此总时间复杂度是线性的，非常高效。
• 空间复杂度：O(V)，用于存储 dist 数组、拓扑序以及图本身（邻接表）。
• 与最短路径的关系：
  • 如果将所有权重取相反数（乘-1），那么求“最长路径”就变成了在新图上求“最短路径”。
  • 在 DAG 上，单源最短路径问题（即使是边权为负）也可以用完全相同的拓扑排序+DP方法解决，只需将 max 操作改为 min 操作，并将初始化值改为 +∞ 即可。
  • 因此，DAG 上的单源最长路径和单源最短路径问题，本质上是一个问题，可以用同一套方法解决。

总结
DAG 上的单源最长路径问题，因其无环的特性，避免了无穷解和复杂的最优子结构破坏。通过拓扑排序确定计算顺序，再应用基于“松弛”思想的动态规划，我们可以在 O(V+E) 的线性时间内高效求解。这个方法也清晰地揭示了最长路径和最短路径在该特定图结构上的对称性与可解性。