Ford算法在有向无环图（DAG）中的单源最短路径问题 题目描述 给定一个 有向无环图 ，其顶点数为 \( n \)，边数为 \( m \)，每条边都有一个权重（可为负），并指定一个源点 \( s \)。要求计算从源点 \( s \) 到图中 所有其他顶点 的最短路径距离。如果从 \( s \) 无法到达某个顶点，则其距离为无穷大；如果图中存在从 \( s \) 可达的负权环，该问题无解（但DAG本身无环，因此这里主要是为了处理负权边）。 题目分析 在有向无环图中，我们可以利用其 无环 的特性，在比 Dijkstra 或 Bellman-Ford 更短的时间内解决单源最短路径问题。由于没有环，我们不需要像 Bellman-Ford 那样进行多轮松弛，也不需要担心负权环。核心思想是：按照 拓扑排序 的顺序处理顶点，确保在处理一个顶点时，所有可能到达它的顶点的最短距离已经被计算出来。 解题步骤 拓扑排序 首先对有向无环图进行拓扑排序，得到一个顶点序列。拓扑排序保证了对于图中的任意有向边 \( (u, v) \)，顶点 \( u \) 在序列中都出现在顶点 \( v \) 之前。 这意味着，当我们按照这个序列的顺序处理顶点时，对于当前顶点 \( v \)，所有可能通过边直接到达它的顶点 \( u \) 都已经被处理过（即它们的初始最短距离估计值已经计算，尽管可能尚未达到最终值）。 初始化 创建一个数组 dist[] ，长度为 \( n \)，用于存储从源点 \( s \) 到每个顶点的最短距离估计值。 将 dist[s] 初始化为 0。 将其他所有顶点的 dist[v] 初始化为无穷大（在代码中可以用一个很大的数，如 INF 表示）。 按拓扑序松弛 按照步骤1得到的拓扑序列，依次处理每个顶点 \( u \)。 对于当前顶点 \( u \)，遍历它的 每一条出边 \( (u, v) \)，其权重为 \( w \)。 进行 松弛操作 ：检查如果通过顶点 \( u \) 可以缩短到达 \( v \) 的距离，则更新 dist[v] 。 松弛操作的条件是： dist[u] + w < dist[v] 。如果成立，则令 dist[v] = dist[u] + w 。 这个操作的意义是：既然我们已经确定了（或当前能得到）到达 \( u \) 的最佳路径，那么我们可以尝试用这条路径加上边 \( (u, v) \) 来更新到达 \( v \) 的路径。 结果获取 当处理完拓扑序列中的所有顶点后， dist[] 数组中存储的就是从源点 \( s \) 到所有顶点的最短路径距离。 对于 dist[v] 仍为无穷大的顶点，表示从源点 \( s \) 无法到达该顶点。 算法复杂度 拓扑排序的时间复杂度为 \( O(n + m) \)。 初始化时间复杂度为 \( O(n) \)。 松弛操作会遍历图中的每一条边恰好一次，时间复杂度为 \( O(m) \)。 因此，总时间复杂度为 \( O(n + m) \)，这比用于一般有向图的 Bellman-Ford 算法 \( O(nm) \) 和 Dijkstra 算法（不能处理负权）要高效。 为什么这个算法有效？ 关键点在于 拓扑排序 提供的顺序保证了“无后效性”。当我们处理顶点 \( v \) 时，所有可能“影响” dist[v] 的顶点（即 \( v \) 的入边邻居）都已经被处理过，并且对它们的出边进行了松弛。因为图是无环的，不可能存在一条路径，从 \( v \) 出发，经过若干顶点后又回到 \( v \) 并产生一个更短的距离（即负权环）。所以，当按照拓扑序处理完一个顶点后，它的 dist 值就已经是最终的最短距离，后续不会再被更新。 与 Bellman-Ford 算法的关系 你可以将此算法视为 Bellman-Ford 算法在 DAG 上的一个特化优化版本。Bellman-Ford 算法需要进行 \( n-1 \) 轮松弛（每轮遍历所有边），因为它无法预知边的处理顺序，必须通过多轮迭代来保证最短路径的传播（尤其是当最短路径包含多条边时）。而在 DAG 中，拓扑序天然提供了一个最佳的、无环的处理顺序，使得只需 一轮 按照此顺序的松弛操作即可得到正确结果，并且同样能够处理负权边。