有向无环图（DAG）中的最长路径问题
字数 1276 2025-10-28 08:36:45

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

题目描述
给定一个带权有向无环图（DAG），每个边有一个实数权重（可能为正、负或零）。要求找到图中从任意源点到任意终点的最长路径（即路径上所有边的权重之和最大的路径）。注意：图中无环，因此不存在正权环导致无限长路径的问题。

解题过程

1. 问题分析

  • 关键性质：由于图是无环的，可以通过拓扑排序确定顶点的线性顺序，使得所有边都从排在前面的顶点指向后面的顶点。
  • 动态规划思路：设 dist[v] 表示从某个起点到顶点 v 的最长路径长度。对于每个顶点 v，其 dist[v] 依赖于所有能到达 v 的顶点 u 的 dist[u] 加上边 (u, v) 的权重。
  • 挑战：需要按拓扑顺序处理顶点，确保在计算 v 的最长路径时，所有前驱顶点 u 的最长路径已被计算。

2. 算法步骤

  1. 拓扑排序

    • 使用 Kahn 算法或 DFS 进行拓扑排序，得到顶点序列 topo_order。
    • 例如，对于下图（顶点 A→B 权重 3，A→C 权重 2，B→D 权重 4，C→D 权重 1）： 
      A → B → D
↓    ↑
C ──┘
      拓扑排序结果可能是 [A, B, C, D] 或 [A, C, B, D]。

  2. 初始化距离数组

    • 创建数组 dist，初始化为 -∞（表示不可达）。
    • 若指定起点 s，则设 dist[s] = 0；若求全局最长路径，需添加一个虚拟源点，连接所有顶点（权重 0），并以该点为起点。

  3. 按拓扑顺序更新距离

    • 遍历 topo_order 中的每个顶点 u：
      • 若 dist[u] 不为 -∞，则遍历 u 的所有邻居 v：
        • 若 dist[u] + w(u, v) > dist[v]，则更新 dist[v] = dist[u] + w(u, v)。
    • 此过程保证处理 v 时，所有入边对应的前驱顶点已处理完毕。

  4. 记录路径（可选）

    • 维护 prev 数组，在更新 dist[v] 时记录 v 的前驱顶点 u，最后反向回溯得到路径。

3. 举例说明

以以下 DAG 为例（边权重括号内）：

A --(3)--> B --(4)--> D
  --(2)--> C --(1)---↑

步骤：

  1. 拓扑排序：[A, B, C, D]。
  2. 初始化 dist = [-∞, -∞, -∞, -∞]，设起点 A 的 dist[A] = 0。
  3. 按顺序处理：
    • A：更新 B：0+3=3；更新 C：0+2=2。
    • B：更新 D：3+4=7。
    • C：更新 D：max(7, 2+1)=7（保留原值）。
  4. 结果：从 A 到 D 的最长路径为 A→B→D，长度 7。

4. 复杂度分析

  • 拓扑排序：O(V+E)。
  • 动态规划遍历：每个顶点和边各访问一次，O(V+E)。
  • 总复杂度：O(V+E)，适用于大规模稀疏图。

5. 关键点总结

  • 依赖拓扑排序消除循环依赖。
  • 初始化距离为 -∞ 以处理负权重边。
  • 若需全局最长路径，通过虚拟源点转化为单源问题。

通过以上步骤，可高效求解 DAG 中的最长路径问题。

有向无环图（DAG）中的最长路径问题 题目描述 给定一个带权有向无环图（DAG），每个边有一个实数权重（可能为正、负或零）。要求找到图中从任意源点到任意终点的最长路径（即路径上所有边的权重之和最大的路径）。注意：图中无环，因此不存在正权环导致无限长路径的问题。 解题过程 1. 问题分析 关键性质 ：由于图是无环的，可以通过拓扑排序确定顶点的线性顺序，使得所有边都从排在前面的顶点指向后面的顶点。 动态规划思路 ：设 dist[v] 表示从某个起点到顶点 v 的最长路径长度。对于每个顶点 v ，其 dist[v] 依赖于所有能到达 v 的顶点 u 的 dist[u] 加上边 (u, v) 的权重。 挑战 ：需要按拓扑顺序处理顶点，确保在计算 v 的最长路径时，所有前驱顶点 u 的最长路径已被计算。 2. 算法步骤 拓扑排序 使用 Kahn 算法或 DFS 进行拓扑排序，得到顶点序列 topo_order 。 例如，对于下图（顶点 A→B 权重 3，A→C 权重 2，B→D 权重 4，C→D 权重 1）： 拓扑排序结果可能是 [A, B, C, D] 或 [A, C, B, D] 。 初始化距离数组 创建数组 dist ，初始化为 -∞ （表示不可达）。 若指定起点 s ，则设 dist[s] = 0 ；若求全局最长路径，需添加一个虚拟源点，连接所有顶点（权重 0），并以该点为起点。 按拓扑顺序更新距离 遍历 topo_order 中的每个顶点 u ： 若 dist[u] 不为 -∞ ，则遍历 u 的所有邻居 v ： 若 dist[u] + w(u, v) > dist[v] ，则更新 dist[v] = dist[u] + w(u, v) 。 此过程保证处理 v 时，所有入边对应的前驱顶点已处理完毕。 记录路径（可选） 维护 prev 数组，在更新 dist[v] 时记录 v 的前驱顶点 u ，最后反向回溯得到路径。 3. 举例说明 以以下 DAG 为例（边权重括号内）： 步骤 ： 拓扑排序： [A, B, C, D] 。 初始化 dist = [-∞, -∞, -∞, -∞] ，设起点 A 的 dist[A] = 0 。 按顺序处理： A ：更新 B ： 0+3=3 ；更新 C ： 0+2=2 。 B ：更新 D ： 3+4=7 。 C ：更新 D ： max(7, 2+1)=7 （保留原值）。 结果：从 A 到 D 的最长路径为 A→B→D ，长度 7。 4. 复杂度分析 拓扑排序：O(V+E)。 动态规划遍历：每个顶点和边各访问一次，O(V+E)。 总复杂度： O(V+E) ，适用于大规模稀疏图。 5. 关键点总结 依赖拓扑排序消除循环依赖。 初始化距离为 -∞ 以处理负权重边。 若需全局最长路径，通过虚拟源点转化为单源问题。 通过以上步骤，可高效求解 DAG 中的最长路径问题。