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

题目描述

给定一个有向无环图（DAG），图中有 n 个节点（编号从 0 到 n-1）和若干条有向边。每条边从节点 u 指向节点 v，并且带有一个正权值（表示距离、时间或收益等）。我们需要找出从任意起始节点到任意终止节点的一条路径，使得路径上的边权值之和最大。如果图中有多个起点，我们需找出所有可能路径中的最大权值和。

例如：
节点数 n = 4，边如下：
0 → 1 (权值 5)
0 → 2 (权值 3)
1 → 3 (权值 2)
2 → 3 (权值 1)
那么最长路径是 0 → 1 → 3，权值和 = 5 + 2 = 7。

解题思路

因为图是有向无环图，我们可以用拓扑排序来得到一个节点的线性顺序，使得所有边都从排在前面的节点指向后面的节点。
在这样的顺序下，我们可以用动态规划按顺序计算每个节点的最长路径值。

定义状态：
dp[i] 表示从任意起点到达节点 i 的所有路径中的最大权值和。

状态转移：
对于节点 i，所有能到达它的节点 j（即存在边 j → i），我们可以从 j 转移到 i：

dp[i] = max(dp[i], dp[j] + weight(j, i))

其中 weight(j, i) 是边 j → i 的权值。
由于拓扑顺序保证在处理节点 i 时，所有可能的 j 都已经被处理过，所以 dp[j] 已经计算完成。

初始条件：
如果没有任何边进入节点 i，则 dp[i] = 0（表示从它自身开始，路径权值和为0）。
但注意：如果所有边权为正，最长路径至少为0（只包含一个节点的路径）。

最终答案：
遍历所有节点，取 dp[i] 的最大值。

详细步骤

1. 建图与拓扑排序

我们用邻接表存储图，同时记录每个节点的入度（有多少条边指向它）。
拓扑排序的方法：

• 将所有入度为0的节点加入队列。
• 从队列中取出节点，将其邻接节点的入度减1，如果减后入度为0则加入队列。

这样得到拓扑顺序后，就可以按该顺序进行DP。

2. 动态规划计算

按拓扑顺序遍历节点 u，对于它的每个邻接节点 v（即边 u → v），更新：

dp[v] = max(dp[v], dp[u] + weight(u, v))

因为 u 在 v 之前，dp[u] 已经是最优值。

3. 边界情况

• 如果图是空的（无边），最长路径权值和为0（只有一个节点的路径）。
• 如果图中有多个连通分量，拓扑排序仍适用（因为DAG可以有多入度为0的节点）。
• 所有边权为正，所以路径越长（边数越多）权值和可能越大，但最终路径必须终止于某个节点（无法再往前走）。

4. 示例推演

用刚才的例子：
n=4, edges = [[0,1,5], [0,2,3], [1,3,2], [2,3,1]]

步骤1：建图与入度
邻接表：
0: [(1,5), (2,3)]
1: [(3,2)]
2: [(3,1)]
3: []
入度： indeg[0]=0, indeg[1]=1, indeg[2]=1, indeg[3]=2

步骤2：拓扑排序
初始队列：[0]
处理0：

• 更新节点1：dp[1] = max(dp[1], dp[0]+5) → dp[1]=5
• 更新节点2：dp[2] = max(dp[2], dp[0]+3) → dp[2]=3
  入度更新：indeg[1]=0? 原本1→0? 不对，看上面：
  原来 indeg[1]=1，减去来自0的边后 indeg[1]=0，加入队列。
  原来 indeg[2]=1，减去来自0的边后 indeg[2]=0，加入队列。
  队列变为 [1, 2]

处理1：

• 更新节点3：dp[3] = max(dp[3], dp[1]+2) → dp[3]=7
  入度更新：indeg[3]=2-1=1，还不为0。
  队列变为 [2]

处理2：

• 更新节点3：dp[3] = max(7, dp[2]+1) → dp[3]=max(7, 3+1=4) → 7
  入度更新：indeg[3]=1-1=0，加入队列。
  队列变为 [3]

处理3：无邻接。结束。

此时 dp = [0, 5, 3, 7]
最大值是 7，对应路径 0→1→3。

复杂度分析

• 拓扑排序时间复杂度 O(n + m)，其中 m 是边数。
• DP过程中每条边遍历一次，也是 O(n + m)。
• 总复杂度 O(n + m)，适合较大规模DAG。

代码框架（Python）

from collections import deque, defaultdict

def longest_path_in_dag(n, edges):
    # 建图
    graph = defaultdict(list)
    indeg = [0] * n
    for u, v, w in edges:
        graph[u].append((v, w))
        indeg[v] += 1
    
    # 拓扑排序队列
    queue = deque([i for i in range(n) if indeg[i] == 0])
    dp = [0] * n  # 初始化为0，因为路径可以从任意起点开始
    
    # 拓扑排序 + DP
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    
    return max(dp) if dp else 0  # 如果n=0返回0

# 示例
n = 4
edges = [(0,1,5), (0,2,3), (1,3,2), (2,3,1)]
print(longest_path_in_dag(n, edges))  # 输出 7

变种与扩展

1. 固定起点：如果要求从特定起点 s 出发，只需初始化 dp[s] = 0，其余节点设为 -inf，确保路径必须从 s 开始。
2. 负权边：如果允许负权边，DAG 最长路径仍可用此方法（因为无环，不会有负环），但初始化 dp 为 -inf 并正确更新即可。
3. 输出具体路径：可以另外记录 prev[i] 表示使 dp[i] 最大的前驱节点，最后回溯。
4. 最短路径：如果求最短路径，只需把 max 改为 min，初始化 dp 为 inf（起点为0）。

这样，我们就完成了“DAG 最长路径”问题的讲解。这个算法是动态规划在图上的经典应用，通过拓扑排序保证无后效性，从而高效求解。