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

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

解题过程

1. 问题分析

• 在一般图中，若存在负权边，常用 Bellman-Ford 算法（\(O(VE)\) 时间复杂度）；若无非负权约束，可用 Dijkstra 算法（\(O(E + V\log V)\)）。
• 但 DAG 具有无环的特性，可以通过拓扑排序确定顶点的线性顺序，使得所有边从左指向右。利用此性质，只需按拓扑顺序遍历顶点，即可在 \(O(V+E)\) 时间内解决单源最短路径问题，且能处理负权边。

2. 关键直觉

• 若顶点按拓扑序排列，则从源点 \(s\) 到任意顶点 \(v\) 的最短路径仅由 \(v\) 的前驱顶点决定。
• 按拓扑序处理顶点时，当处理到顶点 \(v\) 时，其所有前驱顶点的最短路径已被计算完成，因此只需一次松弛操作即可确定 \(v\) 的最短路径。

3. 算法步骤
步骤 1：拓扑排序

• 对 DAG 执行拓扑排序，得到顶点的线性序列。若源点 \(s\) 非序列起点，仅需从 \(s\) 开始处理（实际上拓扑序列中 \(s\) 之前的顶点不可达，可直接忽略）。

步骤 2：初始化

• 创建距离数组 dist[]，初始化 dist[s] = 0，其他顶点 dist[u] = ∞。
• 创建前驱数组 pred[] 记录路径（可选）。

步骤 3：按拓扑顺序松弛边

• 遍历拓扑序列中的每个顶点 \(u\)：
  • 若 dist[u] 不为 ∞，则遍历 \(u\) 的所有邻接边 \((u, v, w)\)（权值为 \(w\)）：
    • 若 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w，并记录 pred[v] = u。

4. 示例演示
考虑以下 DAG（边权在括号内），源点为 A：

A → B (3)  
A → C (6)  
B → C (2)  
B → D (4)  
C → D (1)  
C → E (5)  
D → E (2)

步骤执行：

1. 拓扑排序结果：[A, B, C, D, E]
2. 初始化 dist[]：[A:0, B:∞, C:∞, D:∞, E:∞]
3. 处理顶点 A：
   • 更新 B：dist[B] = 3
   • 更新 C：dist[C] = 6
4. 处理顶点 B：
   • 更新 C：3+2=5 < 6 → dist[C]=5
   • 更新 D：dist[D]=3+4=7
5. 处理顶点 C：
   • 更新 D：5+1=6 < 7 → dist[D]=6
   • 更新 E：dist[E]=5+5=10
6. 处理顶点 D：
   • 更新 E：6+2=8 < 10 → dist[E]=8
7. 最终最短路径：
   • A→B: 3
   • A→C: 5
   • A→D: 6
   • A→E: 8

5. 正确性说明

• 无环性保证按拓扑序处理时，到达顶点 \(v\) 的所有路径已在前驱顶点中被完全考虑。
• 动态规划本质：dist[v] 依赖于其前驱顶点的最优解，而前驱已在此前计算完成。

6. 复杂度分析

• 拓扑排序：\(O(V + E)\)
• 初始化：\(O(V)\)
• 松弛操作：每条边恰好处理一次，\(O(E)\)
• 总时间复杂度：\(O(V + E)\)，优于 Bellman-Ford 和 Dijkstra。

7. 边界情况

• 若源点 \(s\) 不可达某些顶点，其距离保持 ∞。
• 负权边不影响正确性，但若存在从 \(s\) 可达的负权环，则图非 DAG（与前提矛盾）。