带权有向无环图中的最长路径问题（DAG，每条边有正权值）

题目描述

我们有一个带权有向无环图（DAG），图中包含 n 个顶点（编号从 0 到 n-1）和 m 条有向边。每条边都有一个正权值（表示距离、成本或收益等）。给定一个起点 s 和一个终点 t，需要找到从 s 到 t 的一条路径，使得该路径上所有边的权值之和最大。如果不存在从 s 到 t 的路径，则结果为 -∞（或根据题意处理）。

这是一个经典的DAG上的动态规划问题，因为图的无环性质确保了我们可以通过拓扑排序的顺序进行递推，从而高效求解最长路径。

解题思路

由于图是 DAG，我们可以先对图进行拓扑排序，得到一个顶点的线性序列。在拓扑序列中，任意一条边 (u, v) 都满足 u 在序列中出现在 v 之前。因此，当我们按照拓扑序依次处理顶点时，到达某个顶点 v 的所有可能的前驱顶点 u 都已经被处理过，这满足了动态规划的无后效性。

状态定义

设 dp[i] 表示从起点 s 到达顶点 i 的最大权值路径和。初始时，除了起点 s 外，其他顶点的 dp 值初始化为 -∞（表示不可达），而 dp[s] = 0（起点本身权值和为0，因为路径权值只计算边，不计算顶点）。

状态转移

对于拓扑序列中的每个顶点 u，我们遍历其所有出边 (u, v, w)，其中 w 是边权值。如果 dp[u] 不是 -∞（即从 s 可以到达 u），则我们可以尝试通过这条边更新 v 的最优解：

\[dp[v] = \max(dp[v], dp[u] + w) \]

这表示：到达 v 的最大权值，要么是已经记录的某个值，要么是通过 u 过来的路径（dp[u] + w）更优。

结果

最终 dp[t] 就是从 s 到 t 的最大权值路径和。如果 dp[t] 仍为 -∞，则说明不存在从 s 到 t 的路径。

循序渐进讲解

我们通过一个具体例子来演示整个过程。

例子

假设 DAG 如下（顶点 0 到 4，起点 s = 0，终点 t = 4）：

• 边：0 → 1 (权值 5)
• 边：0 → 2 (权值 3)
• 边：1 → 3 (权值 2)
• 边：2 → 3 (权值 7)
• 边：3 → 4 (权值 4)
• 边：2 → 4 (权值 1)

图示（括号内为权值）：

0 →(5)→ 1 →(2)→ 3 →(4)→ 4  
 ↓(3)                       ↑  
 2 →(7)→ 3          (1)─────┘  

目标：求从 0 到 4 的最大权值路径。

步骤 1：拓扑排序

首先进行拓扑排序，得到顶点的一个线性序列，使得所有边方向一致。
一种可能的拓扑序：[0, 2, 1, 3, 4]
（注意：拓扑序不唯一，但必须保证每个顶点的前驱都在它之前被处理。）

验证：

• 0 没有前驱，排第一。
• 2 的前驱是 0，已处理。
• 1 的前驱是 0，已处理。
• 3 的前驱是 1 和 2，都已处理。
• 4 的前驱是 2 和 3，都已处理。

排序正确。

步骤 2：初始化 dp 数组

n = 5，起点 s = 0，终点 t = 4。
设一个极小值 NEG_INF = -10^9（代表负无穷，实际中可用 -float('inf') 或足够小的负数）。
初始化：

dp = [NEG_INF, NEG_INF, NEG_INF, NEG_INF, NEG_INF]  
dp[0] = 0

即：
dp[0]=0, dp[1]=-∞, dp[2]=-∞, dp[3]=-∞, dp[4]=-∞

步骤 3：按照拓扑序进行动态规划

遍历拓扑序列 [0, 2, 1, 3, 4]。

1. 顶点 0：

   • 出边：0→1 (5)，更新 dp[1] = max(-∞, 0+5) = 5
   • 出边：0→2 (3)，更新 dp[2] = max(-∞, 0+3) = 3
     当前 dp: [0, 5, 3, -∞, -∞]

2. 顶点 2：

   • 出边：2→3 (7)，更新 dp[3] = max(-∞, 3+7) = 10
   • 出边：2→4 (1)，更新 dp[4] = max(-∞, 3+1) = 4
     当前 dp: [0, 5, 3, 10, 4]

3. 顶点 1：

   • 出边：1→3 (2)，更新 dp[3] = max(10, 5+2) = 10（不变）
     当前 dp: [0, 5, 3, 10, 4]

4. 顶点 3：

   • 出边：3→4 (4)，更新 dp[4] = max(4, 10+4) = 14
     当前 dp: [0, 5, 3, 10, 14]

5. 顶点 4：
   没有出边（或不需要处理）。

最终 dp[4] = 14，即最大权值路径和为 14。

步骤 4：回溯路径（可选）

为了知道具体是哪条路径，我们可以在更新 dp[v] 时同时记录前驱顶点。
根据上述更新过程：

• 4 来自 3（因为 dp[4] = dp[3] + 4 得到 14）
• 3 来自 2（因为 dp[3] = dp[2] + 7 得到 10）
• 2 来自 0
  因此路径为：0 → 2 → 3 → 4，权值和 = 3 + 7 + 4 = 14。

另一条路径 0 → 1 → 3 → 4 权值和 = 5 + 2 + 4 = 11，不是最大。

算法复杂度

• 拓扑排序：O(n + m)
• 动态规划：遍历所有边一次，O(m)
  总时间复杂度：O(n + m)，非常高效。
  空间复杂度：O(n) 存储 dp 和拓扑序。

边界情况与注意事项

1. 负权值：本题要求边权为正，如果允许负权，但图仍是 DAG，该方法依然可用（因为无环，不会出现负权环问题）。
2. 多个起点/终点：如果起点或终点不唯一，可以稍作扩展（例如，虚拟超级起点连接所有起点，权值0）。
3. 不存在路径：若 dp[t] 保持初始的 -∞，则无路径。
4. 大权值溢出：如果权值很大，需使用 long long 等大整数类型。

代码框架（伪代码）

def longest_path_in_dag(n, edges, s, t):
    # 建邻接表
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v, w in edges:
        graph[u].append((v, w))
        indegree[v] += 1
    
    # 拓扑排序
    topo = []
    from collections import deque
    q = deque([i for i in range(n) if indegree[i] == 0])
    while q:
        u = q.popleft()
        topo.append(u)
        for v, w in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    
    # 动态规划
    NEG_INF = -10**18
    dp = [NEG_INF] * n
    dp[s] = 0
    for u in topo:
        if dp[u] == NEG_INF:
            continue  # 从起点不可达 u，跳过
        for v, w in graph[u]:
            if dp[u] + w > dp[v]:
                dp[v] = dp[u] + w
    
    return dp[t] if dp[t] != NEG_INF else -1  # 返回-1表示无路径

总结

这个问题的核心在于利用 DAG 的拓扑序 来保证动态规划的正确性，通过一次线性扫描即可求出最长路径。它广泛应用于项目管理（关键路径法）、任务调度、依赖关系分析等场景。掌握该算法能帮助你解决许多基于有向无环图的最优化问题。