有向无环图（DAG）中的单源最短路径问题 题目描述 给定一个有向无环图（DAG），以及一个源顶点 \(s\)，求从 \(s\) 到图中所有其他顶点的最短路径。图中边的权重可以为正、负或零。如果从 \(s\) 无法到达某个顶点，则其距离为无穷大。要求算法的时间复杂度低于一般图的单源最短路径算法（如 Dijkstra 或 Bellman-Ford）。 解题过程循序渐进讲解 问题特点与核心思路 在有向无环图中，我们可以对顶点进行拓扑排序，得到一个线性序列，使得所有有向边都从序列中较早的顶点指向较晚的顶点。这个性质允许我们按照拓扑顺序，依次处理每个顶点，并更新其邻居的最短距离。因为当处理一个顶点时，所有可能到达它的路径都已经通过前面的顶点计算完毕，所以每个顶点只需被处理一次。这比 Bellman-Ford 算法的 \(O(VE)\) 时间复杂度更优。 算法步骤详解 （1） 拓扑排序 ：对 DAG 执行拓扑排序，得到顶点的一个线性序列。常用方法有基于 DFS 的或 Kahn 算法（基于入度）。 （2） 初始化距离 ：创建距离数组 dist[] ，设 dist[s] = 0 ，其他顶点的距离初始化为无穷大（表示尚未到达）。 （3） 按拓扑顺序松弛边 ：按照拓扑序列的顺序，依次处理每个顶点 u 。对于 u 的每条出边 (u, v) ，执行松弛操作： 如果 dist[u] + weight(u, v) < dist[v] ，则更新 dist[v] = dist[u] + weight(u, v) 。 （4） 结果 ：处理完所有顶点后， dist[] 中就是从源点 \(s\) 到各顶点的最短距离。 为什么正确 由于拓扑序列保证了所有指向顶点 \(v\) 的边都来自序列中在 \(v\) 之前的顶点。当我们按顺序处理到 \(v\) 时，所有可能更新 dist[v] 的顶点都已经被处理过，因此 dist[v] 此时已经是最优值。这个性质使得算法即使存在负权边也能正常工作（而 Dijkstra 不能处理负权边）。 时间复杂度分析 拓扑排序：\(O(V + E)\)。 初始化：\(O(V)\)。 松弛操作：每个顶点被处理一次，每条边被检查一次，因此为 \(O(V + E)\)。 总时间复杂度为 \(O(V + E)\)，这比 Dijkstra 的 \(O((V+E) \log V)\) 和 Bellman-Ford 的 \(O(VE)\) 更优，但仅适用于 DAG。 实例说明 考虑一个 DAG，顶点为 0 到 4，源点为 0。边与权重：0→1(2), 0→2(6), 1→2(3), 1→3(7), 2→3(1), 3→4(5)。拓扑序列为 0,1,2,3,4。 初始化 dist[ 0 ]=0, 其他为 ∞。 处理顶点 0：更新 dist[ 1]=2, dist[ 2 ]=6。 处理顶点 1：更新 dist[ 2]=min(6,2+3)=5, dist[ 3 ]=2+7=9。 处理顶点 2：更新 dist[ 3 ]=min(9,5+1)=6。 处理顶点 3：更新 dist[ 4 ]=6+5=11。 最终最短距离为 [ 0,2,5,6,11 ]。 边界情况与注意事项 如果图中存在从源点不可达的顶点，其距离保持无穷大。 该算法不适用于有环图，因为环会破坏拓扑顺序的依赖关系。 如果需要输出最短路径，可额外维护前驱数组，在更新距离时记录前驱顶点。 如果图中存在负权环，DAG 不可能有环，因此不会出现负权环导致无限循环的问题。 与相关算法的对比 Bellman-Ford ：可处理任意图、检测负权环，但时间 \(O(VE)\)。DAG 最短路径算法是其在无环图上的优化。 Dijkstra ：只适用于非负权边，基于优先队列实现。 DAG 最短路径算法利用了拓扑结构，实现了线性时间复杂度，且允许负权边。