xxx 有向无环图（DAG）中的单源最短路径问题

题目描述
给定一个带权有向无环图（DAG）和一个源顶点 \(s\)，求从 \(s\) 到图中所有其他顶点的最短路径。边的权值可以是正数、负数或零，但图中不能有环（尤其是负权环）。

解题过程

1. 核心思路
   在DAG中，可以通过拓扑排序确定顶点的线性顺序，使得所有边都从左指向右。利用这一性质，我们可以按拓扑顺序依次松弛每个顶点的出边，确保在处理一个顶点时，所有指向它的顶点的最短路径已被计算完成。

2. 步骤详解

   • 步骤1：拓扑排序
     使用深度优先搜索（DFS）或Kahn算法（基于入度）生成拓扑序列。例如，对于下图（顶点A为源点）：

     A → B (权重2)
     A → C (权重1)
     B → D (权重3)
     C → D (权重-1)
     D → E (权重4)
     

     拓扑序列可能为：[A, B, C, D, E]。

   • 步骤2：初始化距离
     设数组 dist[] 存储从源点 \(s\) 到各顶点的最短距离：

     • dist[s] = 0（源点到自身距离为0）
     • 其他顶点初始化为 ∞（表示尚未可达）。

   • 步骤3：按拓扑顺序松弛出边
     遍历拓扑序列中的每个顶点 u，对其每条出边 (u, v) 执行松弛操作：

     如果 dist[u] + weight(u, v) < dist[v]：
         更新 dist[v] = dist[u] + weight(u, v)
         记录 v 的前驱节点为 u（用于重构路径）
     

     由于按拓扑顺序处理，当处理到 u 时，所有指向 u 的路径已被计算，因此 dist[u] 已是最终最短距离。

3. 示例演示
   对上述图以A为源点：

   • 初始化：dist = [A:0, B:∞, C:∞, D:∞, E:∞]
   • 处理A：
     • 松弛A→B：dist[B] = 0 + 2 = 2
     • 松弛A→C：dist[C] = 0 + 1 = 1
   • 处理B：
     • 松弛B→D：dist[D] = 2 + 3 = 5
   • 处理C：
     • 松弛C→D：1 + (-1) = 0 < 5，更新 dist[D] = 0
   • 处理D：
     • 松弛D→E：dist[E] = 0 + 4 = 4
   • 最终结果：[A:0, B:2, C:1, D:0, E:4]

4. 为什么有效？

   • 无环保证：拓扑排序避免了重复处理顶点（如Bellman-Ford需多次迭代）。
   • 负权边兼容：松弛操作不依赖权值正负，但需无环防止负权环导致的无限循环。
   • 时间复杂度：拓扑排序 \(O(V+E)\) + 一次遍历松弛 \(O(V+E)\)，总复杂度为 \(O(V+E)\)，优于Dijkstra（\(O(E+V\log V)\)）和Bellman-Ford（\(O(VE)\)）。

5. 应用场景

   • 项目管理中的关键路径分析（含负权边时仍有效）。
   • 依赖关系图中的最短任务调度。

总结
通过拓扑排序将DAG转化为线性序列，再按顺序松弛出边，即可高效解决含负权边的单源最短路径问题，且无需担心负权环的干扰。