1. 多段图最短路径到底在考什么多段图最短路径问题乍看像是一道普通的最短路实际它是动态规划里非常典型的一类模型。题目通常会给出一张有向无环图顶点被划分成若干个阶段边只从当前阶段指向下一个阶段源点在第一阶段汇点在最后一个阶段。目标很明确从源点走到汇点让整条路径的边权之和最小。这个模型在算法题、数据结构课设、运筹学作业里都常见尤其适合拿来练动态规划的“阶段划分”和“无后效性”这两个核心概念。我第一次接触这类题时脑子里第一反应是Dijkstra。后来把图一画才发现多段图自带拓扑序根本不需要优先队列。它每一个阶段只依赖前一个阶段的最优结果状态转移非常干净。也就是说你只要按阶段从左往右推每个节点记录从源点到它的最短距离最后汇点的值就是答案。相比一般图最短路多段图DP的代码短、边界清楚、复杂度低是理解动态规划的一把好钥匙。这篇文章适合三类人正在准备算法考试的学生、想补动态规划基础的开发者、以及需要把阶段决策问题写成程序的人。我会从建图、状态定义、递推公式、路径回溯、代码实现一直讲到常见坑和测试方法。你不需要先精通动态规划只要知道数组和循环就能跟上。核心关键词就三个多段图、最短路径、动态规划。把这三个词之间的关系吃透这类题基本就稳了。1.1 先把“多段图”画明白多段图英文常叫multistage graph本质是一张有向无环图。它的顶点被分成k个互不相交的阶段通常记作V1、V2、…、Vk。源点s在V1汇点t在Vk。图中的每条边从某个阶段Vi的顶点指向阶段Vi1的顶点或者至少是从编号较小的阶段指向编号较大的阶段。正因为边只往“后面”走图中不可能出现环所以它天然满足动态规划对拓扑序的要求。你可以把多段图想象成一条流水线第一阶段是原料选择第二阶段是粗加工第三阶段是精加工最后阶段是成品输出。每个阶段有若干可选节点节点之间的边表示从一个状态转移到另一个状态的成本。你要做的不是随便走而是按照阶段顺序一步一步选最后让总成本最低。生活里类似的决策很多比如项目分阶段采购、旅行按天规划路线、生产流程按工序选择设备只要阶段之间不回头都可以抽象成多段图。这里有一个容易混淆的点多段图不一定要求每个阶段节点数量相同也不要求所有边都只连接相邻阶段。有些教材定义只允许相邻阶段连边有些题目允许从第i阶段跳到第i2甚至更后面。只要整体阶段编号递增并且没有回头边动态规划仍然成立。区别在于如果允许跨阶段你更新dp时不能只遍历上一阶段而要按拓扑序更新所有可达后继。不过大多数考试题为了简化都会限制成相邻阶段连边。1.2 动态规划为什么比Dijkstra更贴题Dijkstra当然能求多段图最短路前提是边权非负。它的复杂度是O((VE)logV)用堆优化后也不差。但放在多段图上Dijkstra有点“杀鸡用牛刀”。因为多段图的节点已经按阶段排好了你不需要每次找当前距离最小的未访问节点只需要按阶段顺序扫描。每个节点被访问一次每条边被松弛一次复杂度就是O(VE)。对于节点数上万、边数几万的多段图这个差距会很明显。更关键的是动态规划帮你保留了“阶段决策”的信息。Dijkstra只告诉你最终最短距离是多少而多段图DP可以顺便记录每个节点是从哪个前驱来的回溯出完整路径。如果你需要知道每个阶段选了哪个节点或者需要统计最短路径条数DP的扩展性更好。Dijkstra也能记录前驱但它的松弛顺序是全局的不像多段图这样一层一层推进理解起来更绕。我个人的判断标准很简单如果图是有向无环图并且节点能自然分层优先考虑拓扑DP如果图有环、边权非负、只求单源最短路用Dijkstra如果要求所有点对最短路节点又不多Floyd更省事。多段图最短路径问题属于第一类所以标准解法就是动态规划而不是把Dijkstra硬套上去。1.3 这类题的输入长什么样典型的题目输入会先给阶段数k、节点数n、边数m然后给每个阶段包含哪些节点最后给m条边每条边是u、v、w表示从u到v有一条权值为w的有向边。也有的题目直接给邻接矩阵矩阵中第i行第j列是边权无边用无穷大表示。还有的题目节点编号本身就按阶段排列比如1到3是第一阶段4到6是第二阶段你不需要额外读阶段数组只要按编号顺序更新即可。输入格式不同处理方式略有差别。如果给了阶段数组那就按阶段数组的顺序遍历如果没给阶段数组但节点编号已经按阶段排好直接从小到大遍历节点也能得到正确结果因为所有边都指向编号更大的节点。最怕的是节点编号没按阶段排边又乱给这时你必须先按阶段信息确定拓扑序否则DP会出错。我见过不少同学在这里翻车图是连通的边权也没问题但答案偏大原因就是某个节点的dp值还没算出来就被后继拿去用了。另外要注意源点和汇点的位置。多数题默认源点是第一阶段唯一节点汇点是最后一个阶段唯一节点。但有些题会有多个源点或多个汇点这时可以加一个虚拟源点连向所有源点边权为0再加一个虚拟汇点所有汇点连向它。这样做的好处是统一模型不用在代码里写一堆特判。虚拟源点和虚拟汇点不改变最短路径的值只是让DP的起点和终点更干净。2. 动态规划建模阶段、状态与递推动态规划建模的第一步永远是定义状态。多段图最短路径的状态定义非常直接设dp[v]表示从源点s到节点v的最短距离。源点的dp[s]0其他节点初始化为无穷大。然后按照阶段顺序对每个节点u用它的所有出边去更新后继节点v如果dp[u]w(u,v)小于dp[v]就更新dp[v]同时记录pre[v]u。这个过程从左往右推最后dp[t]就是源点到汇点的最短路径长度。这个递推式的正确性依赖于最优子结构。任何一条从s到t的最短路径如果它经过节点v那么从s到v的那一段也一定是从s到v的最短路径。否则你可以把更短的那段替换进去得到一条更短的全局路径矛盾。再加上多段图没有环节点按阶段排列计算dp[v]时它依赖的所有前驱都已经算完所以不存在“用未来更新过去”的问题。这就是动态规划里说的无后效性。如果你习惯从后往前思考也可以定义反向状态f[v]表示从节点v到汇点t的最短距离。汇点的f[t]0然后从最后一个阶段倒着往前推f[u]min{w(u,v)f[v]}其中v是u的后继。最后f[s]就是答案。向前推和向后推本质一样只是方向不同。向前推更符合“从起点出发”的直觉向后推在路径回溯时有时更方便。考试时选一种你顺手的就行但不要两种混着写。2.1 向前递推从源点往汇点推向前递推的公式可以写成dp[s] 0 dp[v] min{ dp[u] w(u,v) }其中u是v的前驱实际写代码时通常反过来遍历u的出边来更新v。按阶段从1到k-1对当前阶段的每个节点u如果dp[u]不是无穷大就遍历它的所有出边(u,v,w)。这个顺序保证u的dp值已经确定因为u的前驱都在更早的阶段。对于相邻阶段的多段图当前阶段只会更新下一阶段对于允许跨阶段的图当前阶段可能更新后面多个阶段但只要保证阶段递增仍然正确。这个写法有一个小优势你不需要显式地写“min over前驱”。如果每个节点有多条入边用出边更新会自动比较所有前驱。代码结构就是两层循环加一层边遍历非常清晰。复杂度是O(VE)因为每个节点最多被处理一次每条边最多被松弛一次。空间复杂度是O(VE)邻接表存图dp和pre各一个数组。需要注意如果图中存在入度为0但不是源点的节点它的dp会一直是无穷大遍历它的出边时应该跳过。有些实现忘了判断dp[u]INF结果用无穷大去加权重可能溢出或者得到错误值。尤其是用int时INF加一个正数会溢出成负数然后错误地更新其他节点。稳妥的做法是选一个足够大的INF比如0x3f3f3f3f并且在更新前检查dp[u]是否小于INF。2.2 反向递推从汇点往源点回推反向递推的状态是f[v]从v到汇点的最短距离。边界是f[t]0其他节点初始化为无穷大。然后按阶段从k-1倒着推到1对每个节点u遍历它的出边(u,v,w)做f[u] min(f[u], w f[v])最后f[s]就是答案。这种写法的好处是当你要输出路径时从s开始每次选择一个满足w(u,v)f[v]f[u]的后继v就能一路走到t。因为f[v]已经是从v到终点的最优值所以沿着这个条件走每一步都是最优决策。路径回溯不需要额外的pre数组只需要一遍正向扫描。反向递推在有些题目里更自然。比如题目要求输出从源点到汇点的路径并且希望按字典序最小的路径这时你可以从s开始每次在满足等式的后继中选编号最小的那个直接得到字典序最小路径。如果用向前递推你需要先记录pre再从t回溯等长路径的处理会麻烦一些。两种方法都值得掌握面试时如果面试官问你“能不能不记录前驱输出路径”反向递推就是一个很好的回答。不过反向递推也有一个细节你必须确保所有后继的f值已经算好。对于多段图按阶段倒序处理就能保证这一点。如果图不是按阶段存储而是只给了邻接表那你需要先做一次拓扑排序或者按节点编号倒序处理前提是编号满足拓扑序。否则f[v]可能还是无穷大导致f[u]更新错误。这个坑和向前递推是镜像的本质都是拓扑序问题。2.3 路径记录数组的细节向前递推时pre[v]记录的是“v是从哪个前驱来的”。初始化pre所有元素为-1源点的pre保持-1。每次更新dp[v]时令pre[v]u。注意只有严格更短时才更新还是等长时也更新取决于题目要求。如果只求一条最短路径严格更短更新即可如果要求字典序最小路径等长时可能要比较前驱编号或路径序列。大多数基础题只要求输出任意一条最短路径所以严格更短更新就够了。回溯时从汇点t开始不断令curpre[cur]直到cur变成-1或到达源点。把经过的节点存进数组最后反转输出。这里有个常见错误循环条件写成while(cur!s)但pre[s]可能是-1导致死循环或者漏掉s。更稳的写法是while(cur!-1)在循环内把cur加入路径如果curs就break。或者先判断pre[cur]!-1再走。代码不长但边界条件很多建议单独写一个函数测试。如果图中有多条最短路径pre数组只保留最后更新它的那个前驱。由于我们按阶段顺序遍历等长路径中后面被遍历到的前驱可能覆盖前面的所以输出的路径不保证字典序。如果你需要特定顺序可以在更新条件里加入额外判断当dp[u]w dp[v]时直接更新当dp[u]w dp[v]时比较u和pre[v]的大小或者比较完整路径。这个技巧在竞赛题里很常用但基础题不用过度设计。3. 手算一个多段图把DP表铺开光看公式容易飘我们拿一个具体例子走一遍。假设有一张5阶段多段图源点是1汇点是10。阶段划分如下阶段1只有节点1阶段2有节点2、3、4阶段3有节点5、6、7阶段4有节点8、9阶段5只有节点10。边和权重都是正数具体如下表。我们先用向前递推算一遍再用反向递推验证最后回溯路径。这个例子节点不多但包含了汇合点、多条等长路径和路径选择非常适合练手。手算时建议画一张表每一行是一个阶段每一列是一个节点表格里填dp值。每填一个节点标注它是从哪个前驱来的。这样算完一遍路径自然就出来了。我备考时习惯用铅笔在纸上画擦改方便比直接在代码里调试快得多。3.1 样例图与阶段划分样例边如下起点终点权重12213414325726427635336237445446147558359468669278779581039104所有边都从前一阶段指向后一阶段符合多段图定义。源点1的dp[1]0。阶段2的节点2、3、4只能从1来所以dp[2]2dp[3]4dp[4]3。接下来阶段3的节点5、6、7分别有来自2、3、4的入边需要取最小值。再往后阶段4、阶段5同理。整张图没有环也没有负权但就算有负权只要阶段顺序正确这个DP依然能处理。3.2 逐阶段更新距离阶段3计算节点5从2来是279从3来是437从4来是347所以dp[5]7pre[5]可以记3或4。节点6从2来是246从3来是426从4来是314所以dp[6]4pre[6]4。节点7从2来是268从3来是448从4来是358所以dp[7]8pre[7]可以记2、3或4。阶段4计算节点8从5来是7310从6来是4610从7来是8715所以dp[8]10pre[8]记5或6。节点9从5来是7411从6来是426从7来是8513所以dp[9]6pre[9]6。阶段5计算节点10从8来是10313从9来是6410所以dp[10]10pre[10]9。最终答案是从1到10的最短距离为10。你可以看到阶段4的节点8虽然从两个前驱都能得到10但节点9明显更优最终汇点选择了节点9。这说明每一步局部最优不一定全局最优但动态规划把所有可能都保留了所以不会漏掉全局最优。3.3 回溯路径与验证从汇点10开始回溯pre[10]9pre[9]6pre[6]4pre[4]1。所以路径是1 - 4 - 6 - 9 - 10。验证权重1到4是34到6是16到9是29到10是4总和312410和dp[10]一致。这条路径在每个阶段都选了当时的最优前驱但注意节点5和节点8也参与了竞争最终被淘汰是因为后续边权更大。如果你用反向递推从汇点往前算f值f[10]0f[8]3f[9]4f[5]min(33,44)6f[6]min(63,24)6f[7]min(73,54)10f[2]min(76,46,610)13f[3]min(36,26,410)9f[4]min(46,16,510)7f[1]min(213,49,37)10。结果同样是10。反向递推的f[1]10而且你可以从1开始每次选择满足wf[v]f[u]的后继得到1-4-6-9-10路径一致。手算一遍之后你会发现多段图DP的计算量其实很小核心就是按阶段填表。真正容易出错的地方不在公式而在实现时的下标、初始化和遍历顺序。下一步我们把这些细节落到代码里。4. 代码落地C和Python两套模板写代码之前先把输入输出格式定下来。为了通用我建议用邻接表存图用stage数组记录每个阶段包含哪些节点。节点编号从1开始0号不用。源点默认为1汇点默认为n。如果是多个源点或汇点提前加虚拟点处理。dp数组初始化为INFpre数组初始化为-1。然后按阶段从1到k-1遍历对每个节点u如果dp[u]不是INF就遍历它的出边更新后继。最后输出dp[n]和路径。C和Python的写法几乎一样区别只在语法。C适合竞赛速度快Python适合快速验证和面试手写。下面两套模板都经过我实际测试直接替换边数据就能跑。注意代码中不要用mermaid这里只有普通代码块。4.1 C邻接表写法#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int main() { int k, n, m; cin k n m; // 阶段数、节点数、边数 vectorvectorint stages(k 1); for (int i 1; i k; i) { int cnt; cin cnt; for (int j 0; j cnt; j) { int v; cin v; stages[i].push_back(v); } } vectorvectorpairint,int adj(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; adj[u].push_back({v, w}); } vectorint dp(n 1, INF), pre(n 1, -1); dp[1] 0; for (int s 1; s k; s) { for (int u : stages[s]) { if (dp[u] INF) continue; for (auto [v, w] : adj[u]) { if (dp[u] w dp[v]) { dp[v] dp[u] w; pre[v] u; } } } } cout 最短距离: dp[n] endl; vectorint path; int cur n; while (cur ! -1) { path.push_back(cur); if (cur 1) break; cur pre[cur]; } reverse(path.begin(), path.end()); cout 路径: ; for (int i 0; i (int)path.size(); i) { if (i) cout - ; cout path[i]; } cout endl; return 0; }这段代码的关键点是按阶段遍历。阶段数组stages[1]到stages[k]分别存每个阶段的节点。循环只到k-1因为最后一个阶段没有后继需要更新。如果某个节点dp为INF说明从源点不可达直接跳过。pre数组只在严格更短时更新保证路径不会乱。最后从n回溯如果图不连通dp[n]可能是INF路径数组也会异常实际做题时要根据题目保证连通性。4.2 Python写法与调试输出INF 10 ** 18 def solve(k, n, m, stages, edges): adj [[] for _ in range(n 1)] for u, v, w in edges: adj[u].append((v, w)) dp [INF] * (n 1) pre [-1] * (n 1) dp[1] 0 for s in range(1, k): for u in stages[s]: if dp[u] INF: continue for v, w in adj[u]: if dp[u] w dp[v]: dp[v] dp[u] w pre[v] u print(最短距离:, dp[n]) path [] cur n while cur ! -1: path.append(cur) if cur 1: break cur pre[cur] path.reverse() print(路径:, - .join(map(str, path))) return dp[n], path # 样例数据 k 5 n 10 m 20 stages [ [], # 0号不用 [1], # 阶段1 [2, 3, 4], # 阶段2 [5, 6, 7], # 阶段3 [8, 9], # 阶段4 [10] # 阶段5 ] edges [ (1, 2, 2), (1, 3, 4), (1, 4, 3), (2, 5, 7), (2, 6, 4), (2, 7, 6), (3, 5, 3), (3, 6, 2), (3, 7, 4), (4, 5, 4), (4, 6, 1), (4, 7, 5), (5, 8, 3), (5, 9, 4), (6, 8, 6), (6, 9, 2), (7, 8, 7), (7, 9, 5), (8, 10, 3), (9, 10, 4) ] solve(k, n, m, stages, edges)Python版本更紧凑适合在面试白板上手写。调试时可以在每轮阶段后打印dp数组看看每个节点的值是否符合手算结果。比如在for s循环末尾加一行print(s, dp)能快速定位哪一阶段开始偏大。注意INF要设得足够大Python的整数不会溢出但C用int时要注意。如果边权可能达到1e9节点数1e5总和可能到1e14这时得用long long。4.3 滚动数组与空间优化多段图有一个很好的性质每个阶段只依赖前一个阶段所以如果只求最短距离不要求输出路径可以用两个数组滚动更新。设dist表示当前阶段各节点的最短距离next_dist表示下一阶段。遍历当前阶段的每个节点u用dist[u]更新下一阶段的v。当前阶段处理完后把next_dist赋给dist清空next_dist。这样空间从O(V)降到O(最大阶段节点数)对于阶段很宽的图能省不少内存。但滚动数组有一个限制它要求边只连接相邻阶段。如果允许跨阶段你不能再只保留上一阶段因为节点可能依赖更早阶段的值。这时候还是得老老实实用全局dp数组。另外滚动数组不保留历史dp值回溯路径会变得困难。如果需要输出路径建议保留pre数组或者用反向递推加正向扫描。工程里如果只关心数值滚动数组是很好的优化竞赛里如果内存限制宽松用全局dp更省心。我一般这样取舍题目只问最短距离节点数很大用滚动数组题目要求输出路径或统计方案数用全局dp加pre。不要为了炫技把代码写复杂多段图本身复杂度已经很低可读性比省一点内存更重要。5. 常见错误与排查清单多段图DP的代码短但短代码不代表不会错。我见过很多人在样例上跑对一交就WA最后发现是阶段顺序、初始化或路径记录的问题。这一章把典型错误整理成清单你可以对照自己的代码逐条检查。每一条都是实际踩过的坑不是泛泛而谈。5.1 阶段顺序错乱最隐蔽的WA最隐蔽的错误是阶段顺序。如果你的节点编号没有按阶段排列而你又直接写for u in 1..n去更新就会出现某个节点的dp还没算出来就被后继节点拿去用了。比如节点5属于阶段3节点2属于阶段2但编号5大于2如果你按编号从小到大遍历先遍历到节点2没问题但假设某条边从阶段3指向阶段4而阶段4的节点编号比阶段3小按编号遍历就会先处理阶段4导致它用到未更新的阶段3值。解决方法是严格按阶段数组遍历或者先对图做拓扑排序。如果你不想读阶段数组也可以把所有节点按阶段编号排序生成一个拓扑序然后按这个顺序更新。很多题目默认节点编号就是拓扑序但如果你不确定最好显式处理。检查方法打印每个节点的dp值看看是否有节点的dp在它所有前驱之前就被更新了。更简单的方法是手算一个小样例如果手算结果和程序一致阶段顺序大概率没问题。5.2 初始化与无穷大老生常谈但总有人翻车初始化错误主要有三种。第一种是把dp数组全部初始化为0结果每个节点都从0开始加答案当然错。第二种是INF设得太小比如用1000000但实际最短路径可能超过这个值。第三种是忘记把源点dp设为0导致整个数组全是INF最后输出INF。正确做法dp所有元素初始化为INF源点dp设为0pre初始化为-1。INF可以选0x3f3f3f3f约10亿如果边权总和可能超过10亿就改用0x3f3f3f3f3f3f3f3f或者LLONG_MAX/2。还有一个细节用INF去做加法时如果INF是0x3f3f3f3f加上一个正数不会溢出但如果你用INT_MAX加任何正数都会溢出成负数。所以要么在更新前判断dp[u] ! INF要么选一个安全的INF。我习惯在遍历出边前加一句if(dp[u] INF) continue;这样既避免溢出也略微提升效率。Python没有溢出问题但也要跳过INF不然无穷大加权重还是无穷大逻辑上没错但可能掩盖不可达节点。5.3 路径回溯pre数组的三种错法路径回溯的错法也很典型。第一种是pre更新条件写错比如写成if(dp[u]w dp[v])等长路径不断覆盖虽然不影响距离但可能让pre指向一个同阶段节点导致回溯时反复横跳。第二种是回溯循环条件写错比如while(cur ! 1)但pre[1]没设好或者while(pre[cur] ! -1)漏掉最后一个节点。第三种是忘记反转路径输出从汇点到源点的倒序。检查方法先验证路径上相邻节点之间确实有边再把边权加起来看是否等于dp[n]。我建议单独写一个getPath函数输入pre数组和n返回路径向量。在函数里先检查dp[n]是否为INF如果是就返回空。然后从n开始每次把cur加入路径如果cur1就break否则curpre[cur]。如果cur变成-1还没到1说明pre链断了这时可以返回空或报错。最后反转路径。这个函数可以独立测试不用每次都跑整个DP。6. 对比与扩展多段图DP还能怎么用多段图最短路径问题虽然小但它背后连着一大片知识点。你把它学透之后可以自然扩展到最长路径、路径计数、字典序路径、资源约束DP等。在工程里阶段决策、流水线调度、分层网络规划也会用到类似思路。这一章把多段图DP和其他最短路算法放一起对比再聊聊常见的扩展方向帮你建立知识网络。6.1 和Dijkstra、Floyd、Bellman-Ford放一起看算法适用图型时间复杂度负权边多段图上的表现多段图DP有向无环、阶段明确O(VE)可处理负权最优代码短Dijkstra非负权图O((VE)logV)不能可用但没必要Floyd任意图、全源最短路O(V^3)可处理负权太慢不适合大图Bellman-Ford任意图、单源最短路O(VE)可处理负权可用但比DP慢拓扑排序DP任意DAGO(VE)可处理负权多段图是其特例从表里能看出多段图DP和拓扑排序DP本质是一家人。多段图只是DAG的一种特点在于节点天然分层所以你不需要额外做拓扑排序按阶段遍历就行。Dijkstra在多段图上也能用但它没有利用阶段信息复杂度更高。Floyd适合节点数很少且要求所有点对最短路的场景。Bellman-Ford适合有负权环检测的通用图多段图没有环用不上。如果面试官问你“为什么不用Dijkstra”你可以回答Dijkstra的核心是每次选距离最小的未确定节点而多段图的节点已经按阶段排好距离最小的节点一定在当前阶段的最左端不需要堆来维护。直接用阶段遍历复杂度从O(ElogV)降到O(E)。这个回答既准确又体现你对算法本质的理解。6.2 从最短路径扩展到最长路径与计数多段图DP的框架很容易改。求最长路径时把min改成maxdp初始化为负无穷源点dp0。因为图是无环的最长路径不会无限增长所以不需要担心正环。求最短路径条数时增加一个cnt数组。当dp[u]w dp[v]时dp[v]更新cnt[v]cnt[u]当dp[u]w dp[v]时cnt[v]cnt[u]。注意cnt可能会很大竞赛题通常要求取模。求字典序最小路径时可以在等长时比较路径序列或者反向递推时每次选编号最小的后继。这些扩展在考试里经常出现。比如“求最短路径有多少条”“求字典序最小的最短路径”“求经过节点数最少的最短路径”。核心思路都是保留多个状态在转移时增加判断条件。多段图的结构让这些扩展变得很自然因为每个阶段只依赖前一个阶段不会出现循环依赖。6.3 工程与竞赛里的典型场景工程上多段图模型可以描述很多阶段决策问题。比如项目分阶段采购设备每个阶段有多个供应商选择不同供应商的成本不同阶段之间有兼容性约束目标是最小化总成本。再比如旅行路线规划把行程分成若干天每天选择城市城市之间的交通费用是边权求总费用最小的路线。这些问题的共同点是阶段明确、决策有序、不能回头正好是多段图的用武之地。竞赛里多段图最短路径经常作为动态规划入门题出现也经常被包装成“机器人的路线选择”“流水线调度”“资源分配”等背景。有些题会结合状态压缩比如每个阶段有多个任务选择任务会消耗资源要求资源不超过上限这时就在多段图DP上加一维资源状态。还有些题会结合概率求最大概率路径把乘法换成加法取对数即可。万变不离其宗按阶段划分状态用前一阶段的最优值更新当前阶段。7. 我的实操心得与测试建议最后这部分聊聊我实际做这类题时的一些习惯。多段图DP不难但想写得又快又对还是得有一套自己的流程。我一般先画图再手算两三个节点确认递推式没错然后写代码。代码写完后不急着交先造几组边界数据跑一跑。下面这些经验都是踩坑之后总结的你直接拿去用能省不少时间。7.1 造测试数据别只测样例样例通常太顺测不出问题。我习惯造这几类数据第一类只有一条路径的图用来验证基本流程第二类有多条等长最短路径的图用来检查pre覆盖和路径输出第三类存在不可达节点的图用来检查INF处理第四类节点编号顺序和阶段顺序不一致的图用来检查遍历顺序第五类边权为0或负数的图用来检查INF和更新条件。每类数据手算一个预期结果和程序输出对比。举个例子只有一条路径的图1-2-3-4权重都是1答案应该是3路径1-2-3-4。不可达图1-23-4源点1汇点4答案应该是INF程序应该输出不可达而不是乱走。等长路径1-2-4和1-3-4权重都是2程序应该输出其中一条距离为2。把这些数据都跑一遍基本能覆盖90%的边界情况。7.2 调试DP打印表格比单步更有效调试动态规划时单步跟踪容易迷失在循环里。我更喜欢在每轮阶段结束后打印整个dp数组然后和手算的表格对照。如果某一阶段开始出现偏差就聚焦到那一阶段的节点检查它的所有入边。比如手算dp[5]7程序输出9说明更新节点5时用了错误的前驱或者某个前驱的dp还没算好。这时可以把节点5的所有入边打印出来看看每条边的dp[u]w是多少。另一个技巧是写一个print_dp函数按阶段分组打印而不是按节点编号打印。这样一眼就能看出哪个阶段的哪个节点出了问题。如果图比较大还可以只打印当前阶段的节点和后继节点。Python里可以用pprintC里就手动格式化。调试代码不用写得漂亮能快速定位问题就行。7.3 面试或课堂讲解的顺序如果面试被问到这道题我建议按这个顺序讲先定义多段图说明它是有向无环图且节点分层然后定义状态dp[v]为源点到v的最短距离写出递推式dp[v]min(dp[u]w)说明按阶段遍历保证拓扑序复杂度O(VE)再提一下路径回溯用pre数组最后对比Dijkstra强调多段图DP的优势。这样讲逻辑清楚面试官能看出你不仅会写代码还理解为什么这么写。课堂上讲解时可以先用一个生活例子引入比如“从家到公司要经过几个换乘点每个换乘点有不同路线怎么选总时间最短”。然后画图标出阶段带着学生手算一遍。手算之后再上代码学生更容易接受。我试过这种讲法比直接甩公式效果好得多。多段图最短路径问题本身不难难的是让初学者理解“阶段”和“无后效性”所以例子越具体越好。我自己现在遇到这类题第一反应就是先画阶段图把源点和汇点标出来然后从源点开始一层一层往右推。推的时候顺手在纸上记下每个节点的dp值和前驱算完汇点路径也自然出来了。这套流程用熟了基本不会出错。如果你刚开始学建议也用手算几遍再动手写代码比直接抄模板理解得深。