有向无环图（DAG）中单源最短路径问题的动态规划解法

字数 2569 2025-12-13 12:57:55

有向无环图（DAG）中单源最短路径问题的动态规划解法

题目描述
给定一个有向无环图（DAG），其中每条边都有一个权重（可正可负），以及一个源点。要求计算出从源点到图中所有其他顶点的最短路径长度。如果从源点无法到达某个顶点，则其最短路径为无穷大；如果图中存在从源点可达的负权边，但由于图是无环的，因此不存在负权环，最短路径仍然是有定义的。

解题过程循序渐进讲解

第一步：理解问题特性与核心思路
这是一个单源最短路径问题，但图具有特殊的性质——有向无环图（DAG）。
关键特性：

无环：不存在从一个顶点出发经过若干条边后又回到该顶点的路径。
有向：边有方向。
权重可为任意实数（包括负数）。

在一般图中，如果存在负权边，常用的Dijkstra算法无法直接使用，而Bellman-Ford算法虽然能处理负权，但时间复杂度较高（O(VE)）。
但对于DAG，我们可以利用其拓扑序特性，通过动态规划在线性时间内解决问题。

核心动态规划思想：

定义 dist[v] 为从源点 s 到顶点 v 的最短路径长度。
如果已知所有能到达 v 的顶点的最短距离，则 dist[v] 可以通过其前驱节点的距离加上边的权重来更新。
如何保证在计算 dist[v] 时，其所有前驱节点的距离都已计算出来？按照拓扑排序的顺序依次计算即可。

第二步：拓扑排序
由于图是DAG，必然存在拓扑排序。拓扑排序是将图中所有顶点排成一个线性序列，使得对于任意有向边 (u, v)，u 在序列中都出现在 v 的前面。
这意味着，按照这个顺序处理顶点时，当处理到 v 时，所有可能到达 v 的顶点（即 v 的前驱）都已经被处理过了。这正是动态规划所需要的“无后效性”。

拓扑排序可以通过DFS或BFS（Kahn算法）实现，时间复杂度为 O(V+E)。

第三步：动态规划状态转移
假设我们已经得到了拓扑序列 topo_order[0..V-1]。
初始化：

创建数组 dist[0..V-1]，初始值设为无穷大（表示不可达）。
dist[s] = 0，源点到自身的距离为0。

状态转移：
按照拓扑序列的顺序，依次处理每个顶点 u。
对于 u 的每一条出边 (u, v)，执行松弛操作：

如果 dist[u] + weight(u, v) < dist[v]：
    dist[v] = dist[u] + weight(u, v)

为什么按照拓扑序处理是正确的？
因为当处理顶点 u 时，所有可能更新 dist[u] 的前驱节点都已经被处理过了（它们在拓扑序中位于 u 之前），因此 dist[u] 已经达到了最小值。此时利用 u 去更新其后继节点 v 是安全的。

第四步：算法步骤详述
输入：图 G=(V, E)，边权函数 w，源点 s。
输出：从 s 到所有顶点的最短距离数组 dist[]。

对图 G 进行拓扑排序，得到顶点序列 topo_order。
初始化 dist[v] = ∞ 对所有 v ∈ V，dist[s] = 0。
对于拓扑序列中的每一个顶点 u（按顺序）：
1. 如果 dist[u] 仍为 ∞，说明从 s 不可达 u，跳过（因为即使处理它的出边，也无法更新后继节点）。
2. 否则，对于每条以 u 为起点的有向边 (u, v)：
  1. 计算候选距离 new_dist = dist[u] + w(u, v)。
  2. 如果 new_dist < dist[v]，则更新 dist[v] = new_dist。
返回 dist[]。

时间复杂度：

拓扑排序：O(V+E)。
动态规划更新：每条边被检查一次，O(E)。
总时间复杂度：O(V+E)，线性时间，非常高效。

第五步：正确性简要论证
归纳基础：

源点 s 的距离为 0，正确。
归纳步骤：
假设按照拓扑序处理到顶点 v 时，所有能到达 v 的顶点的最短距离都已正确计算。
由于图中无环，任何从 s 到 v 的最短路径的最后一个内部顶点（即 v 的前驱）必然在拓扑序中位于 v 之前，因此该前驱的最短距离已被计算，并且通过松弛操作更新了 v 的距离。
因此，当处理 v 时，dist[v] 已经被所有可能的前驱更新过，从而得到了正确的最短距离。

第六步：实例演示
考虑以下 DAG（顶点编号 0..4），源点为 0：
边：0→1 (5), 0→2 (3), 1→2 (2), 1→3 (6), 2→3 (7), 2→4 (4), 3→4 (1)。
（括号内为边权）

拓扑序（一种可能的）：[0, 1, 2, 3, 4]。

初始化：dist = [0, ∞, ∞, ∞, ∞]。

按拓扑序处理：

u=0: dist[0]=0。
更新边 0→1: dist[1] = min(∞, 0+5)=5。
更新边 0→2: dist[2] = min(∞, 0+3)=3。
u=1: dist[1]=5。
更新边 1→2: dist[2] = min(3, 5+2)=3（不变）。
更新边 1→3: dist[3] = min(∞, 5+6)=11。
u=2: dist[2]=3。
更新边 2→3: dist[3] = min(11, 3+7)=10。
更新边 2→4: dist[4] = min(∞, 3+4)=7。
u=3: dist[3]=10。
更新边 3→4: dist[4] = min(7, 10+1)=7（不变）。
u=4: 无出边，跳过。

最终 dist = [0, 5, 3, 10, 7]。

第七步：与Bellman-Ford算法的对比

Bellman-Ford算法可用于任何有向图（可处理负权，检测负权环），但时间复杂度为 O(VE)。
本方法仅适用于DAG，但利用拓扑序将复杂度降至 O(V+E)，是更高效的特例解法。
如果图中存在环，则无法得到拓扑序，本方法不适用。

总结
对于有向无环图（DAG）的单源最短路径问题，我们可以将动态规划与拓扑排序结合：

通过拓扑排序确定顶点处理顺序，保证无后效性。
按照该顺序对每条边进行一次松弛操作，即可求出所有最短路径。
该方法高效、直观，是处理DAG上最短路径（包括负权边）的标准算法。

有向无环图（DAG）中单源最短路径问题的动态规划解法题目描述给定一个有向无环图（DAG），其中每条边都有一个权重（可正可负），以及一个源点。要求计算出从源点到图中所有其他顶点的最短路径长度。如果从源点无法到达某个顶点，则其最短路径为无穷大；如果图中存在从源点可达的负权边，但由于图是无环的，因此不存在负权环，最短路径仍然是有定义的。解题过程循序渐进讲解第一步：理解问题特性与核心思路这是一个单源最短路径问题，但图具有特殊的性质—— 有向无环图（DAG）。关键特性：无环：不存在从一个顶点出发经过若干条边后又回到该顶点的路径。有向：边有方向。权重可为任意实数（包括负数）。在一般图中，如果存在负权边，常用的Dijkstra算法无法直接使用，而Bellman-Ford算法虽然能处理负权，但时间复杂度较高（O(VE)）。但对于DAG，我们可以利用其拓扑序特性，通过动态规划在线性时间内解决问题。核心动态规划思想：定义 dist[v] 为从源点 s 到顶点 v 的最短路径长度。如果已知所有能到达 v 的顶点的最短距离，则 dist[v] 可以通过其前驱节点的距离加上边的权重来更新。如何保证在计算 dist[v] 时，其所有前驱节点的距离都已计算出来？按照拓扑排序的顺序依次计算即可。第二步：拓扑排序由于图是DAG，必然存在拓扑排序。拓扑排序是将图中所有顶点排成一个线性序列，使得对于任意有向边 (u, v) ， u 在序列中都出现在 v 的前面。这意味着，按照这个顺序处理顶点时，当处理到 v 时，所有可能到达 v 的顶点（即 v 的前驱）都已经被处理过了。这正是动态规划所需要的“无后效性”。拓扑排序可以通过DFS或BFS（Kahn算法）实现，时间复杂度为 O(V+E)。第三步：动态规划状态转移假设我们已经得到了拓扑序列 topo_order[0..V-1] 。初始化：创建数组 dist[0..V-1] ，初始值设为无穷大（表示不可达）。 dist[s] = 0 ，源点到自身的距离为0。状态转移：按照拓扑序列的顺序，依次处理每个顶点 u 。对于 u 的每一条出边 (u, v) ，执行松弛操作：为什么按照拓扑序处理是正确的？因为当处理顶点 u 时，所有可能更新 dist[u] 的前驱节点都已经被处理过了（它们在拓扑序中位于 u 之前），因此 dist[u] 已经达到了最小值。此时利用 u 去更新其后继节点 v 是安全的。第四步：算法步骤详述输入：图 G=(V, E)，边权函数 w，源点 s。输出：从 s 到所有顶点的最短距离数组 dist[ ]。对图 G 进行拓扑排序，得到顶点序列 topo_ order。初始化 dist[ v] = ∞ 对所有 v ∈ V，dist[ s ] = 0。对于拓扑序列中的每一个顶点 u（按顺序）：如果 dist[ u ] 仍为 ∞，说明从 s 不可达 u，跳过（因为即使处理它的出边，也无法更新后继节点）。否则，对于每条以 u 为起点的有向边 (u, v)：计算候选距离 new_ dist = dist[ u ] + w(u, v)。如果 new_ dist < dist[ v]，则更新 dist[ v] = new_ dist。返回 dist[ ]。时间复杂度：拓扑排序：O(V+E)。动态规划更新：每条边被检查一次，O(E)。总时间复杂度：O(V+E)，线性时间，非常高效。第五步：正确性简要论证归纳基础：源点 s 的距离为 0，正确。归纳步骤：假设按照拓扑序处理到顶点 v 时，所有能到达 v 的顶点的最短距离都已正确计算。由于图中无环，任何从 s 到 v 的最短路径的最后一个内部顶点（即 v 的前驱）必然在拓扑序中位于 v 之前，因此该前驱的最短距离已被计算，并且通过松弛操作更新了 v 的距离。因此，当处理 v 时，dist[ v ] 已经被所有可能的前驱更新过，从而得到了正确的最短距离。第六步：实例演示考虑以下 DAG（顶点编号 0..4），源点为 0：边：0→1 (5), 0→2 (3), 1→2 (2), 1→3 (6), 2→3 (7), 2→4 (4), 3→4 (1)。（括号内为边权）拓扑序（一种可能的）：[ 0, 1, 2, 3, 4 ]。初始化：dist = [ 0, ∞, ∞, ∞, ∞ ]。按拓扑序处理： u=0: dist[ 0 ]=0。更新边 0→1: dist[ 1 ] = min(∞, 0+5)=5。更新边 0→2: dist[ 2 ] = min(∞, 0+3)=3。 u=1: dist[ 1 ]=5。更新边 1→2: dist[ 2 ] = min(3, 5+2)=3（不变）。更新边 1→3: dist[ 3 ] = min(∞, 5+6)=11。 u=2: dist[ 2 ]=3。更新边 2→3: dist[ 3 ] = min(11, 3+7)=10。更新边 2→4: dist[ 4 ] = min(∞, 3+4)=7。 u=3: dist[ 3 ]=10。更新边 3→4: dist[ 4 ] = min(7, 10+1)=7（不变）。 u=4: 无出边，跳过。最终 dist = [ 0, 5, 3, 10, 7 ]。第七步：与Bellman-Ford算法的对比 Bellman-Ford算法可用于任何有向图（可处理负权，检测负权环），但时间复杂度为 O(VE)。本方法仅适用于DAG，但利用拓扑序将复杂度降至 O(V+E)，是更高效的特例解法。如果图中存在环，则无法得到拓扑序，本方法不适用。总结对于有向无环图（DAG）的单源最短路径问题，我们可以将动态规划与拓扑排序结合：通过拓扑排序确定顶点处理顺序，保证无后效性。按照该顺序对每条边进行一次松弛操作，即可求出所有最短路径。该方法高效、直观，是处理DAG上最短路径（包括负权边）的标准算法。