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

题目描述
给定一个有向无环图（DAG）和一个源顶点s，图中每条边都有一个权重（可能是负数），要求找出从源顶点s到图中所有其他顶点的最短路径。如果从s无法到达某个顶点，则报告该情况。

关键特性
由于图是有向无环的，我们可以利用其拓扑排序的特性来高效解决最短路径问题。与Dijkstra算法（不能处理负权边）和Bellman-Ford算法（时间复杂度较高）相比，基于拓扑排序的方法能在O(V+E)时间内解决问题，并且能够处理负权边。

解题过程

第一步：理解拓扑排序与最短路径的关系
拓扑排序是DAG中顶点的一种线性排序，使得对于任何有向边(u, v)，u在排序中都出现在v之前。这个特性非常关键：当我们按照拓扑顺序处理顶点时，对于每个顶点v，所有指向v的边都来自在拓扑排序中位于v之前的顶点。这意味着当我们处理顶点v时，我们已经处理完了所有可能到达v的顶点，因此可以确定到v的最短距离。

第二步：算法步骤详解

1. 拓扑排序
   首先需要对DAG进行拓扑排序。可以使用Kahn算法或基于DFS的算法：

   • 计算每个顶点的入度
   • 将入度为0的顶点加入队列
   • 从队列中取出顶点，将其加入拓扑序列，并将其邻接顶点的入度减1
   • 重复直到队列为空

2. 初始化距离数组
   创建一个数组dist[]，其中dist[v]表示从源点s到顶点v的最短距离：

   • dist[s] = 0（源点到自身的距离为0）
   • 对于所有其他顶点v，dist[v] = ∞（初始时设为无穷大）

3. 按照拓扑顺序处理顶点
   按照拓扑排序的顺序依次处理每个顶点：

   • 对于当前顶点u，遍历它的所有邻接顶点v
   • 对于每条边(u, v)，如果dist[u] + weight(u, v) < dist[v]，则更新dist[v] = dist[u] + weight(u, v)
   • 同时记录前驱顶点，用于重构最短路径

第三步：具体示例演示

考虑以下DAG（边上的数字表示权重）：

    1      6       1
0 -----> 1 -----> 3 -----> 4
|        |        ^
| 2      | 2      |
|        |        |
------> 2 --------
    4       1

源点s = 0

1. 拓扑排序：可能的拓扑序列为[0, 1, 2, 3, 4]

2. 初始化：dist = [0, ∞, ∞, ∞, ∞]

3. 处理顶点0：

   • 边0→1：dist[1] = min(∞, 0+1) = 1
   • 边0→2：dist[2] = min(∞, 0+4) = 4
   • 更新后：dist = [0, 1, 4, ∞, ∞]

4. 处理顶点1：

   • 边1→3：dist[3] = min(∞, 1+6) = 7
   • 边1→2：dist[2] = min(4, 1+2) = 3
   • 更新后：dist = [0, 1, 3, 7, ∞]

5. 处理顶点2：

   • 边2→3：dist[3] = min(7, 3+1) = 4
   • 更新后：dist = [0, 1, 3, 4, ∞]

6. 处理顶点3：

   • 边3→4：dist[4] = min(∞, 4+1) = 5
   • 更新后：dist = [0, 1, 3, 4, 5]

7. 处理顶点4：没有出边，无需更新

最终结果：从顶点0到各顶点的最短距离为[0, 1, 3, 4, 5]

第四步：算法正确性分析

算法的正确性基于DAG的拓扑性质：

• 当我们处理顶点v时，所有可能到达v的路径都已经被考虑
• 因为所有指向v的边都来自拓扑排序中在v之前的顶点
• 当我们按拓扑顺序处理时，确保在计算dist[v]之前，所有可能的dist[u]（其中u→v存在边）都已经是最优解

第五步：时间复杂度分析

• 拓扑排序：O(V + E)
• 初始化距离数组：O(V)
• 处理每个顶点和每条边：O(V + E)
• 总时间复杂度：O(V + E)，这比Dijkstra算法的O((V+E)logV)和Bellman-Ford算法的O(VE)都要高效

第六步：应用场景

该算法特别适用于：

1. 项目调度中的关键路径分析
2. 依赖关系图中的最优路径规划
3. 任何需要处理带权DAG且可能有负权边的最短路径问题

关键优势：能够高效处理DAG中的最短路径问题，包括负权边的情况，而不会陷入负权环的问题（因为DAG中不可能有环）。