Ford 算法求解有向无环图（DAG）中单源最短路径问题
字数 1933 2025-12-15 23:12:12

Ford 算法求解有向无环图（DAG）中单源最短路径问题

题目描述

给定一个有向无环图（DAG），图中每条边都有一个权重（可以是正、负或零）。同时给定一个源点 \(s\)。要求计算从源点 \(s\) 到图中所有其他顶点的最短路径长度。如果某个顶点从 \(s\) 不可达，则其最短路径长度为无穷大；如果图中存在从 \(s\) 出发可达的负权环，则在 DAG 中该情况不可能出现，因为 DAG 中不存在任何环。

解题思路

在一般图中，单源最短路径常用 Dijkstra（边权非负）或 Bellman-Ford（允许负权边）算法。但对于 DAG，我们可以利用其无环特性，先进行拓扑排序，然后按照拓扑顺序对顶点进行松弛操作。这种方法称为 Ford 算法（有时称 DAG 最短路径算法）。它的时间复杂度为 \(O(V + E)\)，优于 Bellman-Ford 的 \(O(VE)\)，且能正确处理负权边。

步骤详解

步骤 1：理解 DAG 的特性

  • 有向无环图（DAG）中，不存在任何有向环。
  • 因此，可以对其顶点进行拓扑排序，得到一个顶点序列，使得所有有向边都从序列中前面的顶点指向后面的顶点。
  • 这个性质保证了：当我们按照拓扑顺序处理顶点时，到达当前顶点的所有可能的前驱顶点都已经被处理过。

步骤 2：算法流程

  1. 对 DAG 进行拓扑排序，得到一个顶点序列。
  2. 初始化距离数组 dist[]：
    • dist[s] = 0
    • 对于其他所有顶点 \(v \neq s\)，dist[v] = ∞
  3. 按照拓扑顺序遍历每个顶点 \(u\)：
    • 对于 \(u\) 的每条出边 \((u, v, w)\)（表示从 \(u\) 到 \(v\) 的边，权重为 \(w\)）：
      • 如果 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w（这称为“松弛”操作）。

步骤 3：为什么这样是对的？

  • 由于拓扑排序保证了所有指向顶点 \(v\) 的边都来自序列中 \(v\) 之前的顶点，当我们处理到 \(v\) 时，所有可能更新 dist[v] 的前驱顶点都已经被处理过了。
  • 因此，只需要一遍拓扑顺序的松弛，就能得到所有最短路径，无需像 Bellman-Ford 那样进行多轮松弛。
  • DAG 中无环，所以不可能出现负权环，因此最短路径总是良定义的。

示例演示

考虑以下 DAG（顶点编号 0~4，源点为 0）：

边与权重：
0 -> 1, w = 5
0 -> 2, w = 3
1 -> 3, w = 6
1 -> 2, w = 2
2 -> 4, w = 4
2 -> 3, w = 7
3 -> 4, w = -1

步骤 1：拓扑排序
一种可能的拓扑序：[0, 1, 2, 3, 4]。

步骤 2：初始化距离

dist = [0, ∞, ∞, ∞, ∞]

步骤 3：按拓扑顺序松弛

  • 处理顶点 0：
    • 边 0→1：dist[1] = min(∞, 0+5) = 5
    • 边 0→2：dist[2] = min(∞, 0+3) = 3
  • 处理顶点 1：
    • 边 1→3：dist[3] = min(∞, 5+6) = 11
    • 边 1→2：dist[2] = min(3, 5+2) = 3（未更新）
  • 处理顶点 2：
    • 边 2→4：dist[4] = min(∞, 3+4) = 7
    • 边 2→3：dist[3] = min(11, 3+7) = 10
  • 处理顶点 3：
    • 边 3→4：dist[4] = min(7, 10+(-1)) = 7（未更新）
  • 处理顶点 4：无出边。

最终 dist：

顶点:  0   1   2   3   4
dist:  0   5   3  10   7

边界情况与注意事项

  1. 不可达顶点：在初始化时设为 ∞，处理过程中若从未被更新，则保持 ∞。
  2. 负权边：算法允许负权边，且能正确处理。
  3. 多个拓扑序：任意一个拓扑序都可行，因为 DAG 的拓扑序不唯一，但所有拓扑序都满足松弛所需的顺序性质。
  4. 时间复杂度：
    • 拓扑排序：\(O(V + E)\)
    • 松弛：每个边访问一次，\(O(E)\)
    • 总复杂度：\(O(V + E)\)，非常高效。
  5. 空间复杂度：\(O(V)\) 存储距离数组和拓扑序。

与 Bellman-Ford 对比

  • Bellman-Ford 适用于一般有向图，可检测负权环，但复杂度为 \(O(VE)\)。
  • 对 DAG 使用 Ford 算法，利用了无环性质，将复杂度降为线性，且无需检测负环（因为 DAG 中无环）。

总结

对于有向无环图的单源最短路径问题，Ford 算法（按拓扑顺序松弛）是最优选择：

  1. 先拓扑排序。
  2. 按序松弛每条边。
  3. 一次遍历即可得到所有最短路径。
  4. 允许负权边，且复杂度仅为 \(O(V + E)\)。

此算法是动态规划思想在图论中的典型应用：按照拓扑顺序递推，每个顶点的最短路径由其前驱顶点决定。

Ford 算法求解有向无环图（DAG）中单源最短路径问题 题目描述 给定一个 有向无环图（DAG） ，图中每条边都有一个权重（可以是正、负或零）。同时给定一个源点 \( s \)。要求计算从源点 \( s \) 到图中所有其他顶点的最短路径长度。如果某个顶点从 \( s \) 不可达，则其最短路径长度为无穷大；如果图中存在从 \( s \) 出发可达的负权环，则在 DAG 中该情况不可能出现，因为 DAG 中不存在任何环。 解题思路 在一般图中，单源最短路径常用 Dijkstra（边权非负）或 Bellman-Ford（允许负权边）算法。但对于 DAG ，我们可以利用其无环特性，先进行拓扑排序，然后按照拓扑顺序对顶点进行松弛操作。这种方法称为 Ford 算法（有时称 DAG 最短路径算法） 。它的时间复杂度为 \( O(V + E) \)，优于 Bellman-Ford 的 \( O(VE) \)，且能正确处理负权边。 步骤详解 步骤 1：理解 DAG 的特性 有向无环图（DAG）中， 不存在任何有向环 。 因此，可以对其顶点进行 拓扑排序 ，得到一个顶点序列，使得所有有向边都从序列中前面的顶点指向后面的顶点。 这个性质保证了：当我们按照拓扑顺序处理顶点时，到达当前顶点的所有可能的前驱顶点都已经被处理过。 步骤 2：算法流程 对 DAG 进行 拓扑排序 ，得到一个顶点序列。 初始化距离数组 dist[] ： dist[s] = 0 对于其他所有顶点 \( v \neq s \)， dist[v] = ∞ 按照拓扑顺序遍历每个顶点 \( u \)： 对于 \( u \) 的每条出边 \( (u, v, w) \)（表示从 \( u \) 到 \( v \) 的边，权重为 \( w \)）： 如果 dist[u] + w < dist[v] ，则更新 dist[v] = dist[u] + w （这称为“松弛”操作）。 步骤 3：为什么这样是对的？ 由于拓扑排序保证了所有指向顶点 \( v \) 的边都来自序列中 \( v \) 之前的顶点，当我们处理到 \( v \) 时，所有可能更新 dist[v] 的前驱顶点都已经被处理过了。 因此， 只需要一遍拓扑顺序的松弛 ，就能得到所有最短路径，无需像 Bellman-Ford 那样进行多轮松弛。 DAG 中无环，所以不可能出现负权环，因此最短路径总是良定义的。 示例演示 考虑以下 DAG（顶点编号 0~4，源点为 0）： 步骤 1：拓扑排序 一种可能的拓扑序： [0, 1, 2, 3, 4] 。 步骤 2：初始化距离 步骤 3：按拓扑顺序松弛 处理顶点 0： 边 0→1： dist[1] = min(∞, 0+5) = 5 边 0→2： dist[2] = min(∞, 0+3) = 3 处理顶点 1： 边 1→3： dist[3] = min(∞, 5+6) = 11 边 1→2： dist[2] = min(3, 5+2) = 3 （未更新） 处理顶点 2： 边 2→4： dist[4] = min(∞, 3+4) = 7 边 2→3： dist[3] = min(11, 3+7) = 10 处理顶点 3： 边 3→4： dist[4] = min(7, 10+(-1)) = 7 （未更新） 处理顶点 4：无出边。 最终 dist ： 边界情况与注意事项 不可达顶点 ：在初始化时设为 ∞ ，处理过程中若从未被更新，则保持 ∞ 。 负权边 ：算法允许负权边，且能正确处理。 多个拓扑序 ：任意一个拓扑序都可行，因为 DAG 的拓扑序不唯一，但所有拓扑序都满足松弛所需的顺序性质。 时间复杂度 ： 拓扑排序：\( O(V + E) \) 松弛：每个边访问一次，\( O(E) \) 总复杂度：\( O(V + E) \)，非常高效。 空间复杂度 ：\( O(V) \) 存储距离数组和拓扑序。 与 Bellman-Ford 对比 Bellman-Ford 适用于一般有向图，可检测负权环，但复杂度为 \( O(VE) \)。 对 DAG 使用 Ford 算法，利用了无环性质，将复杂度降为线性，且无需检测负环（因为 DAG 中无环）。 总结 对于 有向无环图 的单源最短路径问题， Ford 算法 （按拓扑顺序松弛）是最优选择： 先拓扑排序。 按序松弛每条边。 一次遍历即可得到所有最短路径。 允许负权边，且复杂度仅为 \( O(V + E) \)。 此算法是动态规划思想在图论中的典型应用：按照拓扑顺序递推，每个顶点的最短路径由其前驱顶点决定。