有向无环图（DAG）的单源最长路径问题（基于动态规划） 问题描述 给定一个有向无环图（DAG），其中每条边都有一个实数权重（可以是正、负或零）。我们需要从图中指定的一个源点出发，求出到图中所有其他顶点的最长路径的长度。这里“最长路径”指的是路径上所有边权重之和最大的路径。如果图中存在从源点可达的、但路径长度为负无穷大的路径（即存在无限增大的正环），该问题在DAG中不会发生，因为DAG无环，但路径权值可以为负。如果从源点无法到达某个顶点，通常定义其最长路径长度为负无穷。 解题过程循序渐进讲解 问题理解与关键观察 由于图是无环的，我们可以对顶点进行拓扑排序，得到一个顶点序列，使得所有有向边都从序列中前面的顶点指向后面的顶点。 在最长路径问题中，可以利用“动态规划”思想：设 dist[v] 表示从源点 s 到顶点 v 的最长路径长度。 对于任意顶点 v ，其 dist[v] 只依赖于所有能直接到达 v 的顶点 u （即存在边 u→v ）的 dist[u] 值。具体来说： dist[v] = max{ dist[u] + weight(u, v) } ，其中取所有入边 (u, v) 中的最大值。 这一递推关系成立的前提是，在计算 dist[v] 时，所有可能的 dist[u] 已经被计算出来。这正好可以通过按照拓扑序处理顶点来保证。 算法步骤 a. 初始化 ： 对图中所有顶点进行拓扑排序，得到拓扑序列。 创建数组 dist[] ，长度等于顶点数。将源点 s 的 dist[s] 设为 0，其他所有顶点的 dist[] 初始化为负无穷（表示尚未到达）。 b. 按拓扑序处理顶点 ： 按照拓扑顺序依次处理每个顶点 u 。对于当前顶点 u ，我们检查从 u 出发的所有出边 (u, v) 。 对每条出边 (u, v) ，执行松弛操作： 如果 dist[u] + weight(u, v) > dist[v]，则更新 dist[v] = dist[u] + weight(u, v) 。 注意：这个松弛操作是“用 u 去更新其邻居 v ”，而不是像最短路径中常见的那样用邻居更新自身。 c. 结果 ： 处理完所有顶点后， dist[] 数组中就存储了从源点 s 到每个顶点的最长路径长度。如果某个顶点的 dist 值仍是负无穷，则表示从 s 不可达该顶点。 正确性直观解释 由于拓扑排序保证了处理顶点 u 时，所有能到达 u 的路径上的前驱顶点都已经被处理过（因为任何到达 u 的路径上的顶点都在拓扑序中位于 u 之前），因此当我们用 u 去更新其后继时， dist[u] 已经是最终的最长路径值。 这个算法实际上是对 DAG 进行了一次动态规划，状态转移方程即为上述的 dist[v] = max{ dist[u] + weight(u, v) } 。 与最短路径问题（Dijkstra 或 Bellman-Ford）不同，这里没有“负权边”导致的问题，因为图无环，不会因为正权边而形成无限增大的环（但最长路径问题中，正权环会导致无穷大，而 DAG 无环，所以安全）。 实例演示 考虑一个简单的 DAG，顶点为 A(源点)、B、C、D，边与权重如下： A→B (3) A→C (2) B→D (4) C→D (1) B→C (1) 拓扑序可能是 A, B, C, D（或 A, C, B, D，但需满足边方向）。 初始化：dist[ A ]=0, 其他为 -∞。 处理 A：更新 B=0+3=3，C=0+2=2。 处理 B：更新 D=3+4=7（通过 B→D），C 不变（3+1=4 > 2，但 C 在拓扑序中可能已在 B 前被处理，若先处理 C 则不会用 B 更新 C。实际上最长路径 A→B→C 权值为 4，但若拓扑序为 A,B,C,D，则处理 B 时 C 尚未处理，可更新 C=4）。 处理 C：更新 D=max(7, 4+1=5)=7。 结果：dist[ A ]=0, B=3, C=4, D=7。 最长路径为 A→B→D，总权重 7。 时间复杂度与空间复杂度 拓扑排序时间复杂度为 O(V+E)，其中 V 是顶点数，E 是边数。 动态规划过程中，每个顶点被处理一次，每条边被检查一次，所以也是 O(V+E)。 总时间复杂度为 O(V+E)，空间复杂度为 O(V) 存储 dist 数组和拓扑序列。 扩展与注意 如果要求具体的最长路径而不仅仅是长度，可以在更新 dist[v] 时同时记录前驱顶点 pred[v] = u ，最后通过前驱回溯得到路径。 此算法同样适用于求单源最短路径（只需将初始化改为正无穷，松弛操作改为取更小值），在 DAG 中可处理负权边而无环的限制。 如果图中存在从源点出发的正权环，该问题无解（但 DAG 无环，所以不会发生）。 这个算法结合了拓扑排序与动态规划，是 DAG 上最长（或最短）路径问题的高效解法。