图论动态规划实战：从‘挖地雷’问题看 DAG 上最长路径的 3 个关键步骤

图论动态规划实战：从‘挖地雷’问题看 DAG 上最长路径的 3 个关键步骤

在算法竞赛和实际工程问题中，我们经常会遇到需要处理有向无环图（DAG）上最优路径的问题。这类问题在图论和动态规划的交汇处形成了一个重要的算法范式——DAG上的动态规划。本文将以经典的"挖地雷"问题为例，深入剖析解决DAG最长路径问题的三个核心步骤，并提供一个可复用的算法模板。

1. DAG与动态规划的天然契合

有向无环图（Directed Acyclic Graph, DAG）是一种特殊的有向图，它没有任何有向环。这种无环特性使得DAG具有一些独特的性质，特别是它总是存在拓扑排序——图中顶点的一种线性排序，使得对于图中的每一条有向边(u, v)，u在排序中总是位于v的前面。

DAG与动态规划的结合之所以如此自然，是因为：

1. 无后效性保证：DAG的拓扑序确保了当我们计算某个顶点的状态时，所有可能影响该状态的顶点都已经被处理过
2. 子问题独立性：DAG的结构天然地将问题分解为相互依赖的子问题
3. 高效计算路径：利用DAG的拓扑序可以避免重复计算，实现线性时间复杂度的算法

在"挖地雷"问题中，每个地窖代表图中的一个顶点，地窖之间的通道代表有向边，而地窖中的地雷数量则是顶点的权值。我们的目标是找到一条路径，使得路径上所有顶点权值之和最大。

2. 解决DAG最长路径的三个关键步骤

2.1 状态定义：明确dp数组的含义

在任何动态规划问题中，第一步也是最重要的一步就是定义状态。对于DAG上的最长路径问题，我们通常这样定义状态：

dp[i]: 以顶点i为终点的所有路径中，点权加和最大的路径的点权加和

对于"挖地雷"问题，初始状态很简单：每个顶点自身构成一条路径，因此初始时：

dp[i] = a[i] // a[i]表示顶点i的地雷数量

这种状态定义的关键在于：

• 以终点为导向：便于后续的状态转移
• 包含所有可能性：确保不遗漏任何可能的路径
• 易于扩展：可以方便地记录路径信息

2.2 状态转移方程：建立顶点间的递推关系

状态转移方程是动态规划的核心，它描述了如何从小问题的解构建大问题的解。对于DAG最长路径问题，状态转移基于以下观察：

对于任意顶点v，如果存在边(u, v)，那么以v为终点的最长路径要么是v自身，要么是某个以u为终点的最长路径加上v。

因此，状态转移方程为：

dp[v] = max(dp[v], dp[u] + a[v]) 对于所有存在边(u, v)的u

这个方程可以用自然语言描述为：

以v为终点的最大路径权值，等于所有能到达v的顶点u的最大路径权值加上v自身的权值，再取最大值

在实际编码中，我们通常会在状态转移时同时记录路径信息：

if (dp[v] < dp[u] + a[v]) { dp[v] = dp[u] + a[v]; pre[v] = u; // 记录前驱节点 }

2.3 拓扑序计算：确保正确的计算顺序

DAG动态规划的第三个关键点是按照拓扑序进行计算。这保证了当我们处理一个顶点时，所有可能影响它的顶点都已经被处理过。计算拓扑序有两种主要方法：

1. Kahn算法：通过不断移除入度为0的顶点
2. DFS后序遍历：对图进行深度优先搜索，按照完成时间的逆序排列

对于"挖地雷"问题，如果顶点编号已经构成拓扑序（即所有边都是从小编号指向大编号），我们可以直接按编号顺序处理，否则需要先进行拓扑排序。

以下是使用Kahn算法进行拓扑排序同时完成状态转移的示例：

void topoSort() { queue<int> q; // 初始化：将所有入度为0的顶点加入队列 for(int i = 1; i <= n; ++i) { if(deg[i] == 0) { q.push(i); dp[i] = a[i]; // 初始状态 } } while(!q.empty()) { int u = q.front(); q.pop(); for(int v : adj[u]) { // 遍历u的所有邻接点 if(dp[v] < dp[u] + a[v]) { dp[v] = dp[u] + a[v]; pre[v] = u; // 记录路径 } if(--deg[v] == 0) { q.push(v); } } } }

3. 完整算法模板与实现细节

基于上述三个关键步骤，我们可以提炼出一个解决DAG最长路径问题的通用模板。这个模板分为以下几个部分：

3.1 数据结构准备

const int N = 1e5 + 10; // 根据问题规模调整 vector<int> adj[N]; // 邻接表存图 int a[N]; // 顶点权值 int dp[N]; // dp数组 int pre[N]; // 记录路径前驱 int deg[N]; // 记录入度 int n; // 顶点数

3.2 拓扑排序与动态规划

void solve() { // 初始化dp数组和队列 queue<int> q; for(int i = 1; i <= n; ++i) { if(deg[i] == 0) { q.push(i); dp[i] = a[i]; } } // 拓扑排序+动态规划 while(!q.empty()) { int u = q.front(); q.pop(); for(int v : adj[u]) { if(dp[v] < dp[u] + a[v]) { dp[v] = dp[u] + a[v]; pre[v] = u; } if(--deg[v] == 0) { q.push(v); } } } // 找出最大权值路径的终点 int max_end = 1; for(int i = 2; i <= n; ++i) { if(dp[i] > dp[max_end]) { max_end = i; } } // 输出结果 cout << "最大地雷数: " << dp[max_end] << endl; cout << "路径: "; printPath(max_end); }

3.3 路径输出

路径输出通常需要递归或使用栈来逆序输出：

void printPath(int v) { if(pre[v] != 0) { printPath(pre[v]); cout << "->"; } cout << v; }

或者使用栈的非递归实现：

void printPath(int v) { stack<int> path; while(v != 0) { path.push(v); v = pre[v]; } while(!path.empty()) { cout << path.top(); path.pop(); if(!path.empty()) cout << "->"; } }

4. 算法优化与变种

4.1 空间优化

如果不需要记录具体路径，可以省略pre数组。对于某些特定结构的DAG（如链式结构），还可以进一步优化空间。

4.2 时间优化

对于已知拓扑序的DAG（如顶点编号本身就是拓扑序），可以省略显式的拓扑排序步骤，直接按顺序处理顶点：

for(int u = 1; u <= n; ++u) { for(int v : adj[u]) { if(dp[v] < dp[u] + a[v]) { dp[v] = dp[u] + a[v]; } } }

4.3 处理DAG最短路径

将max改为min，并适当调整初始条件，同样的框架可以解决DAG最短路径问题：

// 初始化 dp[i] = INF; // 对于所有i dp[start] = a[start]; // 状态转移 if(dp[v] > dp[u] + a[v]) { dp[v] = dp[u] + a[v]; }

4.4 多权值扩展

如果需要考虑多种权值（如路径长度和地雷数量），可以扩展dp数组的维度：

struct Node { int mines; // 地雷总数 int steps; // 步数 bool operator<(const Node& other) const { return mines < other.mines; // 或其他比较逻辑 } } dp[N];

5. 实战应用与常见错误

在实际应用中，DAG动态规划经常出现在以下场景：

• 任务调度问题
• 依赖关系解析
• 版本控制系统中的合并问题
• 编译过程中的指令调度

常见错误包括：

1. 忽视DAG的验证：在不是DAG的图上应用此算法会导致错误结果
2. 初始状态设置不当：特别是多源点时的初始化
3. 路径记录不完整：在需要输出路径时忘记维护pre数组
4. 边界条件处理不当：如空图或单点图的特殊情况

对于"挖地雷"问题的完整实现，需要注意输入格式的处理（不同OJ可能有不同要求）以及路径输出的格式要求（如连接符是空格还是短横线）。