寻找有向无环图（DAG）中的最长路径问题 题目描述 给定一个有向无环图（DAG）和图中每条边的权重（可以为正、负或零），我们需要找到从任意一个起点到任意一个终点的最长路径的长度。这里的“最长路径”指的是路径上所有边权重之和最大的路径。由于图是无环的，该问题可以在多项式时间内解决，与一般有向图中最长路径是NP难问题不同。 解题过程 这个问题可以通过动态规划结合拓扑排序来解决。核心思路是：按照拓扑顺序处理顶点，确保在计算某个顶点的最长路径时，所有可能到达它的前驱顶点的最长路径都已计算完毕。 步骤1：拓扑排序 首先，我们需要获取图的拓扑排序序列。拓扑排序能够保证对于任意一条有向边(u, v)，顶点u在序列中都出现在顶点v之前。这为我们后续按顺序进行动态规划提供了基础。 通过BFS（Kahn算法）或DFS实现拓扑排序。这里以DFS为例，但注意要处理可能的不连通图。我们通过递归回溯记录顺序，得到一个拓扑序列。 步骤2：初始化距离数组 我们创建一个数组 dist[] ，其中 dist[i] 表示从任意起点到达顶点i的最长路径长度。 由于我们不知道最长路径从哪个顶点开始，一种常见的技巧是引入一个虚拟源点S，它连接到图中所有顶点，且边的权重为0。这样问题转化为从S到所有顶点的最长路径。 但实际上，我们可以更直接地初始化：将 dist[] 的所有值初始化为负无穷（表示不可达），然后对于每个入度为0的顶点（即没有前驱的顶点），将其 dist 设为0（因为从它自身开始的路径长度为0）。 另一种等价的做法是：不特别区分起点，在动态规划过程中，通过比较所有前驱顶点的距离来更新当前顶点。 步骤3：动态规划递推 按照拓扑顺序遍历每个顶点u。对于u的每个邻居v（即存在有向边u→v），我们尝试用 dist[u] + weight(u,v) 来更新 dist[v] 。即： \[ dist[ v] = \max(dist[ v], dist[ u ] + weight(u,v)) \] 这个递推的意义是：如果通过u到达v能够获得更长的路径，就更新v的最长距离。由于按照拓扑顺序处理，当处理到u时，所有可能到达u的前驱都已经处理过，因此 dist[u] 已经是最终值。 步骤4：获取结果 遍历所有顶点， dist[] 中的最大值就是整个DAG中最长路径的长度。如果需要具体路径，可以在更新 dist[v] 时记录前驱顶点，最后通过前驱信息回溯。 举例说明 考虑一个简单的DAG：顶点0,1,2,3，有向边及权重如下： 0→1 (5), 0→2 (3), 1→2 (2), 1→3 (6), 2→3 (7)。 拓扑排序结果可能是[ 0,1,2,3 ]。 初始化 dist = [-∞, -∞, -∞, -∞] ，将入度为0的顶点0的 dist[0] 设为0。 处理顶点0：更新 dist[1]=5 , dist[2]=3 。 处理顶点1：更新 dist[2] = max(3, 5+2)=7 , dist[3]=5+6=11 。 处理顶点2：更新 dist[3] = max(11, 7+7)=14 。 处理顶点3：无出边。 最终 dist 的最大值是14，即最长路径0→1→2→3，权重和为5+2+7=14。 注意事项 如果图中有多个连通分量，需要确保每个顶点都被处理到（通过遍历所有顶点，只处理已拓扑排序的顶点）。 如果所有权重都为1，那么问题等价于寻找最长路径（以边数计），此时递推公式中权重为1。 此算法的时间复杂度为O(V+E)，其中V是顶点数，E是边数，主要由拓扑排序和动态规划遍历构成。 通过以上步骤，我们可以在有向无环图中高效地找到最长路径。