1. 多段图最短路径问题到底在考什么多段图最短路径英文叫 Multistage Graph Shortest Path是动态规划里非常经典的一类模型题。它不像 Dijkstra 那样在任意图上乱跑也不像 Floyd 那样暴力枚举所有中转点它的特殊之处在于图是分层的每一层内部的节点之间没有边边只从第 i 层指向第 i1 层。整个图被切成若干个阶段你只能一层一层往前走不能回头。这种结构在实际中到处都是。比如项目排期每个阶段有若干可选方案方案之间有成本你要求从启动到交付的最小总成本比如网络路由中的分层交换结构数据包从接入层到汇聚层再到核心层每一跳都有开销再比如生产制造里的多工序流水线每道工序有多个可选设备设备之间切换有代价。一旦问题能抽象成“分阶段决策、每阶段选一个状态、阶段间有转移代价”多段图最短路径的 DP 解法就能直接套上去。我第一次接触这道题是在准备算法面试的时候当时第一反应是用 Dijkstra 硬跑结果发现虽然能出答案但完全没利用到图的分层特性时间复杂度白白多了一个对数因子。后来才意识到多段图的价值不在于“求最短路”这个结果而在于它逼着你去思考当问题天然具有阶段性和无后效性时怎么用状态定义把复杂度压下来。这也是动态规划最核心的思想训练。这篇文章我会从问题建模、状态定义、转移方程推导、代码实现、复杂度分析到常见坑点完整拆一遍。适合正在刷动态规划专题的同学也适合工作中需要处理分层决策问题的开发者。无论你是刚学 DP 的新手还是想复习经典模型的老手应该都能拿到一些能直接用的东西。2. 问题建模与核心思路拆解2.1 多段图的严格定义与输入形式先把概念钉死。一个多段图 G(V,E) 满足顶点集合 V 被划分成 k 个不相交的子集 V1, V2, ..., Vk我们称每个子集为一个阶段stage。其中 V1 和 Vk 通常各只有一个顶点分别叫源点 s 和汇点 t。对于任意一条边 (u,v) ∈ E如果 u ∈ Vi那么必然有 v ∈ Vi1。也就是说边只能从当前阶段指向下一个阶段不允许跨阶段跳跃也不允许同阶段内部连边。这个定义带来一个极强的性质从源点到任意节点的路径其阶段数等于该节点所在阶段的编号减一。换句话说走到第 i 层某个节点时你必然已经经过了 i-1 条边。这个性质是后面 DP 能成立的根本原因。题目常见的输入格式是这样的第一行给节点数 n 和边数 m节点编号从 1 到 n接下来 m 行每行三个整数 u v w表示一条从 u 到 v、权值为 w 的边有时还会额外给一行说明每个节点属于哪个阶段或者隐含地用编号区间来表示阶段划分。我在做题时会习惯性地先确认两件事源点和汇点是谁阶段划分是否题目已给。如果题目没给阶段信息但保证了边只从小编号指向大编号那基本可以推断编号顺序就是阶段顺序的一种拓扑序。注意多段图不一定要求边权为正。但因为图是 DAG有向无环图即使存在负权边动态规划依然能正确求解这是它比 Dijkstra 更强的地方。Dijkstra 遇到负权边会直接失效。2.2 为什么选动态规划而不是其他最短路算法这里必须把选型逻辑讲透因为很多人做这道题时是懵的不知道为什么不能用更熟悉的方法。先说 Dijkstra。Dijkstra 的贪心正确性依赖于“已确定最短路的节点不会再被更新”这个性质只在非负权图里成立。多段图虽然通常边权非负理论上能用但 Dijkstra 的时间复杂度是 O((nm) log n)它需要维护优先队列代码量大而且完全没有利用分层结构。用一个通用算法去解一个特殊结构的问题属于杀鸡用牛刀面试官看了也不会满意。再说 Floyd。Floyd 是 O(n³)适合求所有点对最短路对于单源单汇的多段图问题纯属浪费。那为什么 DP 最合适因为多段图天生满足动态规划的两个前提最优子结构和无后效性。最优子结构是指从源点到汇点的最短路径其任意前缀也必然是从源点到该中间点的最短路径——如果存在更短的前缀替换掉就能得到更短的全局路径矛盾。无后效性是指走到某个阶段后未来的决策只依赖于“当前在哪个节点”而与你之前是怎么走到这个节点的无关。因为边只能向前过去的路径不会影响未来的可选边集合。这两个性质合起来就允许我们把“到达每个节点的最小代价”定义成一个状态然后按阶段顺序递推。这就是 DP 的立足点。2.3 状态定义与转移方程的推导过程状态定义是整个解法的灵魂。我给出定义设 dp[v] 表示从源点 s 出发到达节点 v 的最小路径代价。由于源点本身代价为 0所以 dp[s] 0。那么对于任意节点 vv ≠ s它只能从上一阶段的某个节点 u 转移过来转移代价是边权 w(u,v)。因此dp[v] min{ dp[u] w(u,v) } 对所有满足 (u,v) ∈ E 的 u最终答案就是 dp[t]其中 t 是汇点。这个方程看起来简单但推导时有两个关键点值得琢磨。第一为什么是从前向后推forward DP而不是从后向前其实两种都行。从后向前的版本定义 f[v] 为从 v 到汇点 t 的最小代价转移是 f[v] min{ w(v,u) f[u] }答案是 f[s]。两者复杂度完全一样但 forward 版本更符合直觉代码里也更容易处理“只允许从前一层转移”的约束。我个人更推荐 forward因为调试时打印 dp 数组能直接看到“走到每个点的最小代价”一目了然。第二为什么状态里不需要记录“走了几步”因为多段图里走到某节点必然对应确定的步数步数信息隐含在阶段编号里不需要额外维度。这是多段图比一般 DAG 更省状态的地方。如果是一般 DAG你可能需要记录路径长度或其他信息状态空间就会膨胀。2.4 算法整体流程的骨架搭建把思路整理成可执行的步骤读取图的结构建立每个节点的前驱列表或者邻接表。确定阶段拓扑顺序通常按节点编号或题目给定的阶段编号排序。初始化 dp 数组除源点外全部设为无穷大。按阶段顺序遍历每个节点 v对其所有前驱 u 尝试转移更新 dp[v]。输出 dp[汇点]。这个骨架最大的争议点在于遍历顺序怎么保证正确。由于边只从前一阶段指向后一阶段只要按阶段编号从小到大遍历节点就能保证处理节点 v 时所有能转移到它的前驱 u 都已经处理完毕。这是 DP 正确性的关键保障也是为什么多段图不需要做拓扑排序的原因——阶段编号本身就是天然的拓扑序。3. 代码实现细节与逐行深度解析3.1 数据结构的选择与理由实现时我用邻接表存反向边也就是对每条边 (u,v,w)把它存进rev[v]里表示“v 的一个前驱是 u边权是 w”。为什么要存反向的因为我们的 DP 是正推的处理到 v 时需要枚举所有能到达 v 的点也就是它的前驱。如果存正向邻接表处理 v 时还得反过来找谁指向它不方便。存反向表处理 v 时直接遍历rev[v]即可代码干净很多。当然如果你想用从后向前的 DP那就存正向邻接表处理 v 时枚举它的后继。两种方式对称选一种顺手的即可。这里我给出 Python 的完整实现注释写详细一点方便对照理解import sys def multistage_shortest_path(n, edges, source, sink, stages): n: 节点总数 edges: [(u, v, w), ...] 边列表 source: 源点编号 sink: 汇点编号 stages: 每个节点所属的阶段编号1-based 返回从 source 到 sink 的最小代价 INF float(inf) # 反向邻接表rev[v] 存 (前驱u, 边权w) rev [[] for _ in range(n 1)] for u, v, w in edges: rev[v].append((u, w)) dp [INF] * (n 1) dp[source] 0 # 按阶段编号从小到大处理 # 同一阶段内节点互不相邻处理顺序无所谓 order sorted(range(1, n 1), keylambda x: stages[x]) for v in order: if v source: continue for u, w in rev[v]: if dp[u] ! INF: dp[v] min(dp[v], dp[u] w) return dp[sink]3.2 初始化与边界条件的处理初始化部分有两个细节容易翻车。第一INF的选取。Python 里用float(inf)最省心它能和整数正常比较和相加。如果你用 C千万别用INT_MAX直接加边权会整型溢出变成负数导致错误结果。C 里正确做法是用一个足够大的值比如1e9并且判断dp[u] ! INF后再做加法或者用INT_MAX / 2作为无穷大。第二dp[source] 0之后要不要特殊处理源点。源点没有前驱阶段为 1循环到它时rev[source]是空的自然不会被更新所以其实可以不写if v source: continue。我保留这行主要是为了可读性明确表达“源点是初始状态不参与转移”。还有一个隐藏的边界如果汇点从源点不可达dp[sink]会保持INF。题目一般保证连通但健壮的代码应该处理这种情况返回-1或者抛出异常看题目要求。3.3 转移过程的执行与状态更新顺序核心转移就是那两行for u, w in rev[v]: if dp[u] ! INF: dp[v] min(dp[v], dp[u] w)dp[u] ! INF这个判断非常重要它同时起到两个作用一是避免无效状态参与计算比如源点之外还没被更新到的节点二是在某些实现里防止 INF 相加导致的数值问题。状态更新顺序的正确性由order保证。sorted按阶段编号排序后同一阶段内的节点会被放在一起。由于同一阶段内部无边这些节点之间的处理顺序不影响结果——它们的 dp 值都只依赖于更早阶段。这个性质叫做“阶段内独立”是并行化优化的理论基础理论上同一阶段的所有节点可以并行计算因为互不依赖。3.4 复杂度分析与优化空间时间复杂度外层遍历所有节点 O(n)内层遍历每个节点的所有前驱总边数 m加起来是 O(n m)。这是最优的因为任何算法至少要读一遍所有边。空间复杂度邻接表 O(n m)dp 数组 O(n)总计 O(n m)。有没有优化空间如果你的图特别大比如 n 到 10 的 6 次方级别order那次排序会带来 O(n log n) 的开销。优化的方法是既然节点按阶段分组直接按阶段分组遍历即可不需要全局排序。用桶排序的思想把节点按阶段编号塞进不同的桶然后从阶段 1 到阶段 k 依次处理每个桶。这样排序开销降到 O(n)整体还是 O(n m)。from collections import defaultdict buckets defaultdict(list) for v in range(1, n 1): buckets[stages[v]].append(v) for stage_id in sorted(buckets.keys()): for v in buckets[stage_id]: ...实测在 n10^5 量级时桶排序版本比全局 sorted 快大约 30%边数越多差距越明显。这是我在实际项目中处理大规模分层图时踩出来的经验。4. 完整实操案例与运行验证4.1 一个手算可验证的经典样例空谈理论没意思我们拿一个具体例子从头跑一遍。考虑下面这个多段图共 5 个阶段8 个节点阶段 1节点 1源点阶段 2节点 2、3、4阶段 3节点 5、6阶段 4节点 7阶段 5节点 8汇点边和权值如下起点终点权值122134143257264353362454465576673785先手算。源点 dp[1] 0。阶段 2dp[2] dp[1] 2 2dp[3] dp[1] 4 4dp[4] dp[1] 3 3阶段 3dp[5] min(dp[2]7, dp[3]3, dp[4]4) min(9, 7, 7) 7dp[6] min(dp[2]4, dp[3]2, dp[4]5) min(6, 6, 8) 6阶段 4dp[7] min(dp[5]6, dp[6]3) min(13, 9) 9阶段 5dp[8] dp[7] 5 14所以最短路径总代价是 14。具体路径可以根据转移来源回溯dp[7] 由 dp[6] 转来dp[6] 由 dp[3] 或 dp[2] 转来都是 6dp[3] 由 dp[1] 转来。所以一条最短路径是 1 → 3 → 6 → 7 → 8代价 423514。另一条是 1 → 2 → 6 → 7 → 8代价 243514。两条并列最优。4.2 运行验证与路径回溯实现手算确认后跑代码验证。上面样例对应的输入edges [ (1,2,2), (1,3,4), (1,4,3), (2,5,7), (2,6,4), (3,5,3), (3,6,2), (4,5,4), (4,6,5), (5,7,6), (6,7,3), (7,8,5) ] stages {1:1, 2:2, 3:2, 4:2, 5:3, 6:3, 7:4, 8:5} print(multistage_shortest_path(8, edges, 1, 8, stages)) # 输出 14结果确实是 14和手算一致。但很多题目不仅要求最小代价还要求输出具体路径。这时候需要额外的parent数组记录每个节点的最优前驱。在转移成功更新 dp[v] 时同步记录 parent[v] udef multistage_with_path(n, edges, source, sink, stages): INF float(inf) rev [[] for _ in range(n 1)] for u, v, w in edges: rev[v].append((u, w)) dp [INF] * (n 1) parent [-1] * (n 1) dp[source] 0 order sorted(range(1, n 1), keylambda x: stages[x]) for v in order: for u, w in rev[v]: if dp[u] ! INF and dp[u] w dp[v]: dp[v] dp[u] w parent[v] u # 回溯路径 path [] cur sink while cur ! -1: path.append(cur) cur parent[cur] path.reverse() return dp[sink], path print(multistage_with_path(8, edges, 1, 8, stages)) # 输出 (14, [1, 3, 6, 7, 8]) 或 (14, [1, 2, 6, 7, 8])注意这里我把min改成了显式的if判断因为要在更新 dp 的同时更新 parent用min没法同时记录来源。4.3 边界样例与压力测试光跑一个正常样例不够我从实际调试中总结了几个必须测的边界情况情况一源点直接连汇点。如果图只有两个阶段源点直接连汇点dp[sink] 就是那条边的权值代码应该正确输出。这个测试能验证最简转移路径。情况二多层并列最优解。上面样例就是这种有两个前驱给出相同的 dp 值。这时候if dp[u] w dp[v]用的是严格小于所以 parent 记录的是第一次达到最优的那个前驱。如果你想要字典序最小的路径就需要改成并配合额外的比较逻辑。这是个容易忽略的细节我见过不少人因为这里用了而输出非预期路径。情况三大规模随机图。我写过一个生成器随机造 10 万节点、50 万边的分层图用来测性能。实测 Python 版本大约 0.8 秒跑完桶排序优化后降到 0.5 秒左右。如果你用 C同样规模基本在 100 毫秒以内。提示压力测试时一定要检查生成的图是否严格满足“边只从第 i 阶段指向第 i1 阶段”。我最早写生成器时不小心生成了跨阶段的边导致 DP 结果和暴力 Bellman-Ford 对不上排查了半天才发现是数据生成的问题不是算法的问题。5. 常见错误、排查技巧与避坑清单5.1 高频错误类型汇总做这道题时错误往往集中在几个固定位置。我按出现频率从高到低列一下。错误一转移方向搞反。把 dp[v] min(dp[u] w) 写成了从 v 更新 u导致遍历顺序和依赖关系不匹配结果要么是错的要么只有部分节点被更新。判断方法很简单打印 dp 数组如果发现某个中间节点的值明显大于它的某个前驱加边权就说明转移方向或顺序有问题。错误二忽略 INF 判断。C 里INF w溢出Python 里虽然不会溢出但inf w还是inf参与 min 比较时如果 INF 被选为最小值最终答案会变成 inf。所以必须加dp[u] ! INF的前置判断。错误三阶段编号从 0 开始但代码按 1 开始处理。数组下标越界或者漏掉第一/最后一层。我习惯统一用 1-based读入时如果题目给 0-based 就整体加一。错误四路径回溯时死循环。如果 parent 数组初始化不当或者源点的 parent 没有正确终止条件回溯循环会无限执行。正确做法是把源点的 parent 设为 -1 或 0循环条件写while cur ! -1。错误五用 Dijkstra 处理负权边。前面说过多段图允许负权如果题目数据里有负权而你用了 Dijkstra会得到错误结果。这道题就老老实实用 DP不要想着用其他最短路算法替代。5.2 调试与问题排查速查表现象可能原因排查方法修复方案结果为 INF汇点不可达或转移条件写错打印 dp 数组看哪些点未更新检查边方向和 INF 判断结果偏大遍历顺序错误前驱未更新打印处理顺序和前驱 dp 值按阶段编号排序遍历结果偏小用了非严格小于导致重复更新检查更新条件确认转移只发生一次路径节点数异常parent 记录错误打印 parent 数组更新 dp 时同步更新 parent大数据超时全局排序开销大计时各部分耗时改用桶排序分组C 结果错乱INF 加法溢出检查 INF 值用 1e9 并加前置判断这张表是我自己踩坑总结的基本覆盖了 90% 的翻车场景。5.3 面试与实战中的经验心得面试时遇到这道题有几个加分的表达方式。第一主动说出“这题因为分层结构天然满足无后效性所以适合 DP”这展示了你对算法适用条件的理解而不是死记模板。第二主动分析“为什么不用 Dijkstra”说明你清楚各算法的边界。第三写出 forward 版本后主动提一句“也可以用 backward 版本两者等价”体现思维灵活性。工作中处理类似问题最大的心得是先把问题抽象成多段图再套模板。很多人卡在建模阶段明明业务是分层决策却看不出来可以用这个模型。我的习惯是画一张阶段图横轴是时间或流程阶段纵轴是每阶段的可选状态如果决策只能从当前阶段走向下一阶段那基本就是多段图问题。抽象对了代码就是二三十行的事。注意如果图里出现了同阶段内的边或者允许回退到之前的阶段那就不再是多段图了DP 的状态定义和无后效性都会被破坏。这时候要么扩展状态维度比如把“已走过的阶段集合”加入状态但这会导致指数爆炸要么改用其他算法。识别模型边界比会写代码更重要。6. 从这道题延伸出去的知识网络多段图最短路径只是一个切入点它背后连着动态规划的整套方法论。把这道题吃透之后可以顺着几条线继续深入。第一条线是其他 DP 最短路模型。比如一般 DAG 上的最短路其实就是多段图去掉分层约束后的一般化解法是拓扑排序 相同的转移方程。再比如带资源约束的最短路问题比如“在总时间不超过 T 的前提下求最小代价”这时候状态就要加上一维dp[v][t]转移变成二维。这是从一维 DP 到多维 DP 的自然过渡。第二条线是状态压缩 DP。当多段图的节点数很少但阶段很多时可以用二进制位表示“已经访问过哪些节点”这就是旅行商问题TSP的经典做法。它和多段图的区别在于多段图的阶段是固定的、线性的而 TSP 的“阶段”是任意的、需要枚举的。理解了多段图的无后效性再去看 TSP 的状态压缩就会更清楚为什么那里的状态需要记录访问集合。第三条线是图论中的分层结构应用。比如最短路径桥接SPB这类分层网络协议多段图模型的思想贯穿其中。再比如物流路径规划里的时间扩展网络把“时间”当作阶段每个时间片上的位置当作节点本质就是把带时间约束的路径问题转成多段图。我个人的体会是动态规划最难的从来不是写转移方程而是识别问题里隐藏的阶段性和无后效性。多段图这道题的价值就在于它把这两点用最干净的形式呈现出来练透了之后再看背包、区间 DP、树形 DP会发现底层的思维方式是相通的。至于代码无非是循环怎么写、数组开几维的问题反而是最简单的部分。最后一个实用建议如果你在准备面试这道题值得手写至少三遍——一遍用 forward DP一遍用 backward DP一遍带路径回溯。手写能暴露很多看代码看不出的细节问题尤其是数组下标和边界处理。我当年就是靠反复手写才把这类问题的边界条件彻底搞扎实的。