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

题目描述
给定一个带权有向无环图（DAG），每个边有一个实数权重（可能为正、负或零），要求找出从任意起点到任意终点的最长路径（即边权之和最大的路径）。若图中有正权环，最长路径可能无限长，但题目保证图为DAG，因此不存在环，最长路径必然有限。

解题过程

1. 问题分析

   • 在DAG中，最长路径问题可以通过动态规划高效解决，利用拓扑排序的性质确保计算顺序的正确性。
   • 关键思路：对节点进行拓扑排序后，按顺序遍历节点，用动态规划记录从起点到当前节点的最长路径值。

2. 拓扑排序

   • 首先对DAG进行拓扑排序，得到一个线性序列，使得图中所有边均从序列中靠前的节点指向靠后的节点。
   • 方法：通过DFS或BFS（Kahn算法）实现。以下以Kahn算法为例：
     1. 统计每个节点的入度（指向该节点的边数）。
     2. 将入度为0的节点加入队列，依次处理队列中的节点：
        • 将该节点加入拓扑序列。
        • 将其邻居节点的入度减1，若减至0则加入队列。

3. 动态规划状态定义

   • 设 dist[v] 表示从某个起点（如所有入度为0的节点）到节点 v 的最长路径值。
   • 初始化：所有 dist[v] = -∞（表示初始时不可达），但若起点固定，则起点的 dist 设为0；若起点任意，需特殊处理（见后续步骤）。

4. 动态规划转移

   • 按拓扑顺序遍历每个节点 u：
     • 遍历 u 的所有邻居 v，边权为 w(u, v)。
     • 更新：dist[v] = max(dist[v], dist[u] + w(u, v))。
   • 注意：若要求全局最长路径（起点和终点均任意），需初始化所有 dist[v] = 0（因为路径可以从任意节点开始），但这样会忽略负权边的影响？实际上，应初始化所有 dist[v] = 0，然后按拓扑序更新。但更通用的做法是添加一个“超级源点”：
     • 创建一个虚拟节点 s，连接到所有原节点（边权为0），以 s 为起点，计算到所有节点的最长路径。

5. 超级源点法（通用解法）

   • 步骤：
     1. 在DAG中添加一个虚拟节点 s，并添加从 s 到所有原节点的边，边权为0。
     2. 对扩展后的图进行拓扑排序（s 必为拓扑序首节点）。
     3. 初始化 dist[s] = 0，其他节点 dist[v] = -∞。
     4. 按拓扑序遍历每个节点 u，对每个邻居 v 执行松弛操作：

        if dist[v] < dist[u] + w(u, v):  
            dist[v] = dist[u] + w(u, v)  
        

     5. 全局最长路径即为 max(dist[v])（v为所有原节点）。

6. 路径还原

   • 记录前驱节点 prev[v]：在更新 dist[v] 时，同时记录 prev[v] = u。
   • 从最长路径的终点反向追踪前驱节点，即可得到完整路径。

7. 复杂度分析

   • 拓扑排序：O(V+E)。
   • 动态规划：遍历每个节点和每条边，O(V+E)。
   • 总复杂度：O(V+E)，优于一般图的最长路径算法（一般图需用Bellman-Ford，复杂度为O(VE)）。

示例
假设DAG如下（边权括号内）：

A → B (2)  
A → C (1)  
B → D (3)  
C → D (1)  

• 拓扑排序：[A, B, C, D]（或[A, C, B, D]）。
• 添加超级源点 s，边权为0指向A、B、C、D。
• 计算 dist：
  • dist[s]=0
  • dist[A]=max(-∞, 0+0)=0
  • dist[B]=max(-∞, 0+2)=2（通过A）
  • dist[C]=max(-∞, 0+1)=1（通过A）
  • dist[D]=max(-∞, 2+3=5, 1+1=2)=5（通过B）
• 全局最长路径为5（路径s→A→B→D，忽略s后为A→B→D）。

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