多段图的最短路径是算法课里少数几个看到结构就知道该用什么的题型。只要题目里出现顶点可以划分成若干段、边只能从第 i 段指向第 i1 段这类描述基本可以立刻判定这是动态规划的送分题不需要 Dijkstra不需要堆优化一段循环倒着推一遍就完事。但真到期末编程题或者面试白板上翻车的人一点都不少——有人把顶点编号当成了段号有人 INF 加出负数有人只输出了一条路径却被要求列出所有最优解。这篇就把多段图最短路径从建模、状态定义、递推、决策记录到代码落地整条链路讲清楚顺带把几个我实际踩过的坑摊开说无论你是刚学动态规划的新手还是回头复习算法设计的同学都能直接照着复现。1. 先把多段图这个词拆开顶点分层与边的走向1.1 从一张物流转运表看多段图的真实长相多段图Multistage Graph听起来抽象换成物流场景就很好理解了。假设一批货从产地发往销地中间必须经过若干个转运枢纽第一站只能进集货中心第二站只能进区域分拨第三站只能进城市配送站最后到客户手里。每个阶段的候选节点是明确的而且货只能一站一站往前推不能从区域分拨倒回集货中心。这就是多段图的本质顶点集合被划分成 k 个互不相交的子集边只从第 i 段指向第 i1 段。形式化一点说给定有向图 G(V,E)若存在 V 的一个划分 V1, V2, ..., Vk使得对任意边 (u,v)∈E若 u∈Vi则必有 v∈V(i1)这样的图就叫 k 段图。通常约定 V1 只有一个源点 sVk 只有一个汇点 t中间段的顶点数量不限。为什么强调源点唯一、汇点唯一因为这两个约束直接决定了递推的起止位置——你总得有个地方开始填表也得有个地方让表收敛。我在实际做题时发现很多人读题漏掉边只从第 i 段指向第 i1 段这句把图当成普通带权有向图去做堆优化 Dijkstra 写了一百行结果答案还是对的但老师要看的是 DP 过程分就没了。所以第一步永远是确认这张图到底是不是多段图判断标准很简单能不能给每个顶点标一个段号使得所有边都满足段号 1。如果存在同段之间的边或者跳跃多段的边那就不是标准多段图。1.2 为什么无环这个附加条件才是DP的通行证多段图的边只能往下一段走这个结构天然保证了图中不存在环。这一点非常关键因为动态规划能用的前提就是子问题之间必须有明确的拓扑顺序不能互相依赖。如果有环你算 A 需要 B算 B 又需要 A递推就死锁了只能改用 Bellman-Ford 这类迭代松弛的办法。无环带来的直接好处是我可以给所有顶点排出唯一的推进顺序。反向递推时从汇点往前推正向递推时从源点往后推每一段的顶点在计算时它所依赖的下一段或上一段结果一定已经算好了。这就是所谓的无后效性——顶点 u 的最优决策只取决于它自己到汇点的边的权重以及下一段顶点的最优值跟前面怎么走到 u 的完全无关。打个比方这就像做菜。如果你要做红烧肉你得先焯水、再炒糖色、再炖每一步都依赖前一步的产物顺序明确不会出现炖到一半发现还得回去焯水的情况。动态规划的递推数组就是这些半成品按依赖顺序摆好用的时候直接取。1.3 段与段之间跳过了怎么办阶段划分的两种常见口径教材里画的多段图通常很规整段与段之间边线清清爽爽。但实际题目里经常出现从第 2 段直接连到第 4 段的边或者中间某段只有一两个顶点。这时候阶段划分就有两种处理口径口径做法适用场景注意点严格逐层每段编号连续允许跳段边但要在递推时正确累加题目明确给出段划分递推时不能假设只访问下一段最长路分层用拓扑序给顶点定层层号取所有前驱层号最大值1题目只给图不给段划分分层后可能存在空段压缩层合并只含一个顶点的中间段段数多但逻辑简单做题快但和教材定义有出入我个人的习惯是如果题目已经给了段划分就老实按段循环如果只给了图和边先跑一遍拓扑排序确定层级再按层递推。千万别自己凭顶点编号猜段号这是后面第 5 章要专门讲的坑。分层这件事在写代码时建议用二维列表stages [[...], [...], ...]显式存下来比每次用条件判断去算要清晰得多调试的时候也能直接打印出每段的顶点肉眼核对。2. 反向递推的坐标cost数组和决策数组各管什么2.1 状态定义的那一句话决定了后面所有代码解多段图最短路径第一步是把状态定义写成一句中文。我习惯这么写cost[i] 表示从顶点 i 出发沿任何一条合法路径走到汇点 t 的最小总权值。注意是从 i 出发也就是说这个状态描述的是剩余路程的最优值而不是已经走过的路程。这个方向选对了边界条件就非常干净cost[t] 0因为从汇点走到汇点不需要任何花费。定义完状态递推方程自然就出来了cost[i] min{ w(i, j) cost[j] } 其中 (i,j) ∈ E这里的 w(i,j) 是边权cost[j] 是下一段的已知结果。整个式子翻译成人话就是从 i 出发的最短路等于随便挑一条出边走出去花掉的边权加上从那个落点继续走到终点的最优值在所有出边里取最小的那个。你要是选另一种定义也不违法比如定义 cost[i] 为从源点走到 i 的最短距离那就是正向递推边界变成 cost[s] 0递推式变成 cost[j] min{ cost[i] w(i,j) }。两种定义数学上等价但反向后推的好处是不需要额外的前驱数组就能直接回溯路径正向则必须额外存 prev。这也是为什么大多数教材默认讲反向版本。2.2 决策记录一维nxt够不够什么情况下必须上二维path只求出一个最短距离数字一维的 cost 数组就够了。但题目一旦加一句输出最短路径你就必须额外记录决策。这里有个分层只要求输出任意一条最短路用一维数组nxt[i]记录顶点 i 在最优方案下走到的下一跳最后从源点沿着 nxt 一路跳过去即可。要求输出所有最短路一维不够必须改成best_next[i] [v1, v2, ...]把所有满足w(i,v) cost[v] cost[i]的 v 都收集起来再用 DFS 展开。很多教材里出现的path二维数组比如path[i][j]其实是另一种口径把顶点按第 i 段第 j 个来编号path 存的是这一格该往哪个顶点走。这种二维写法在人工手算时特别舒服因为表格一摊开就能逐格填但写成代码反而绕。我一般只在黑板上手推时用二维落到代码里还是老老实实用一维加列表。这里必须提醒一句用一维 nxt 记录时如果直接写if (new cost[u]) { cost[u] new; nxt[u] v; }遇到相等的情况不更新就会丢掉并列最优解。这道题里最短路可能不止一条比如下面第 3 章要手推的例子就有两条长度相同的路径。想要全部输出判断条件必须写成小于则清空重记等于则追加这个细节后面 5.3 会展开。2.3 边界、INF与初始化三个最容易写反的地方第一个是汇点的初始化。cost[t] 一定是 0不能是 INF。有些同学图省事把整个 cost 数组初始化为 INF然后忘记把汇点改成 0结果所有计算出来都是 INF 权重输出一个大得离谱的数。第二个是不可达的处理。如果某个顶点 i 没有任何出边能通向汇点它的 cost 应该保持 INF并且在参与上一段的 min 比较时被自然排除。注意这里隐含一个前提INF 加上任意有限边权后结果仍然要被认为是不可达。在 Python 里 float(inf) 加任何数还是 inf天然没问题但在 C 或 Java 里用 int 存 INF就可能溢出成负数反而被 min 选中输出一个荒谬的负距离。这个坑 5.2 单独讲。第三个是迭代顺序的边界。反向递推从倒数第二段开始一直推到第 1 段。如果段索引从 0 开始循环就是for k in range(len(stages)-2, -1, -1)很容易写成range(len(stages)-1, -1, -1)多算了一次汇点所在段虽然结果不受影响但逻辑上不干净。正向递推同理从第 2 段推到第 k 段。3. 拿一张12个顶点的图手推一遍从汇点倒着填到源点3.1 建图与阶段表光看公式容易飘找一张经典例题推一遍最踏实。取一个 5 段图的例子顶点编号 1~12段划分为V1 {1}V2 {2, 3, 4, 5}V3 {6, 7, 8}V4 {9, 10, 11}V5 {12}边和权值如下表起点终点权值起点终点权值12969613761051437941527103264810527281162819124362101223771112548115711588这张图的好处是它同时包含了两种典型情况从第 1 段到第 2 段的边比较密集而第 3 段到第 4 段、第 4 段到第 5 段的边比较稀疏能覆盖顶点无出边和多个最优解并列两种情形。3.2 逐段填cost表每一步都写清楚比较过程从最后一段往前推。汇点是 12cost[12] 0。先处理第 4 段 {9, 10, 11}顶点 9唯一出边 9→12 权 4cost[9] 4 0 4决策记为 12。顶点 10唯一出边 10→12 权 2cost[10] 2 0 2决策记为 12。顶点 11唯一出边 11→12 权 5cost[11] 5 0 5决策记为 12。再处理第 3 段 {6, 7, 8}顶点 6两条出边。走 9 是 6 cost[9] 6 4 10走 10 是 5 cost[10] 5 2 7。取小值 7决策记为 10。顶点 7走 9 是 4 4 8走 10 是 3 2 5。取 5决策记为 10。顶点 8走 10 是 5 2 7走 11 是 6 5 11。取 7决策记为 10。第 2 段 {2, 3, 4, 5}顶点 2走 6 是 4 7 11走 7 是 2 5 7走 8 是 1 7 8。取 7决策记为 7。顶点 3走 6 是 2 7 9走 7 是 7 5 12。取 9决策记为 6。顶点 4唯一出边到 811 7 18决策记为 8。顶点 5走 7 是 11 5 16走 8 是 8 7 15。取 15决策记为 8。第 1 段 {1}顶点 1走 2 是 9 7 16走 3 是 7 9 16走 4 是 3 18 21走 5 是 2 15 17。最小是 16而且出现了一次并列走 2 和走 3 都能得到 16。这就是前面反复提到的多解情况。把结果整理成一张表看得更清楚顶点所属段cost 值最优下一跳11162 或 3227732964218852158637107351083710944121042121145121250—3.3 回溯出两条等价最优路径从源点 1 顺着最优下一跳走因为顶点 1 有两个并列决策所以有两条路径1 → 2 → 7 → 10 → 12总权值 9 2 3 2 161 → 3 → 6 → 10 → 12总权值 7 2 5 2 16两条路径长度完全一致。如果你写的程序只吐出来第一条不是算法错了而是决策记录那块用了单值覆盖的写法。另外注意中间顶点 7 和 6 的最优决策都指向 10这是巧合也是必然——10 到汇点的代价只有 2是第 4 段里最便宜的落点所以第 3 段的顶点天然都想往它身上靠。手工推这一步的价值在于你能亲眼看到最优子结构是怎么在两段之间传递的。顶点 6 之所以知道走 10 划算完全依赖 cost[10] 这个已经算好的值如果顺序颠倒过来先算第 3 段再算第 4 段cost[10] 还是 INF结果全错。3.4 如果反过来从源点正推表会长什么样同一张图用正向递推dist[i] 表示源点到 i 的最短距离也能得到 16过程如下。dist[1] 0。第 2 段dist[2] dist[1] 9 9前驱 1dist[3] dist[1] 7 7前驱 1dist[4] dist[1] 3 3前驱 1dist[5] dist[1] 2 2前驱 1第 3 段dist[6] min(dist[2]4, dist[3]2) min(13, 9) 9前驱 3dist[7] min(dist[2]2, dist[3]7, dist[5]11) min(11, 14, 13) 11前驱 2dist[8] min(dist[2]1, dist[4]11, dist[5]8) min(10, 14, 10) 10前驱 2 或 5 并列第 4 段dist[9] min(dist[6]6, dist[7]4) min(15, 15) 15前驱 6 或 7dist[10] min(dist[6]5, dist[7]3, dist[8]5) min(14, 14, 15) 14前驱 6 或 7dist[11] dist[8] 6 16前驱 8第 5 段dist[12] min(dist[9]4, dist[10]2, dist[11]5) min(19, 16, 21) 16前驱 10结果同样是 16。可以看出正向递推的并列情况更多回溯路径时要沿着前驱数组倒着走代码上比反向的 nxt 链要绕一点。如果题目只要求长度两种写法随便挑如果要求输出路径我强烈建议用反向因为 cost 和 nxt 天然是一条顺着走的链从源点一路打出来就是答案不用 reverse。4. 代码落地三种实现写法的取舍与踩坑4.1 邻接矩阵与邻接表的选择依据存储结构这件事多段图里有明确结论稠密用矩阵稀疏用邻接表。上面那张 12 顶点的例子总共 19 条边V² 144用矩阵会浪费大量空间而且反向递推时如果偷懒写成遍历所有顶点 v看 adj[u][v] 是不是 INF复杂度会变成 O(V²) 而不是 O(E)。多段图真正优雅的地方在于顶点 u 的合法后继必然落在下一段里所以只需要遍历stages[k1]这个列表即可复杂度严格是 O(V E)。我见过不少答案代码长这样for u in stages[k]: for v in range(n): if adj[u][v] INF: ...逻辑没错但把一个 O(E) 的算法写成了 O(V²)。期末题数据量小的时候看不出来一旦顶点数上去差距就拉开了。更稳的写法是把邻接表直接按边存好# edges[u] [(v, w), ...] 只包含合法的下一跳 edges {1: [(2,9), (3,7), (4,3), (5,2)], 2: [(6,4), (7,2), (8,1)], ...}这样既省内存又顺便把非法边过滤掉了不用每次都判断 INF。4.2 反向DP的完整Python实现逐行说清下面这份实现假设顶点用 0 起始编号stages 按顺序给出每一段的顶点列表最后一段只有一个汇点。INF float(inf) def multistage_shortest(n, stages, edges): n : 顶点个数编号 0 ~ n-1 stages: 二维列表stages[k] 是第 k 段的顶点按段前缀顺序 edges : 字典edges[u] [(v, w), ...]v 必须在 u 的下一段 返回 : (最短距离, 最优下一跳列表字典) cost [INF] * n nxt [[] for _ in range(n)] sink stages[-1][0] cost[sink] 0 # 从倒数第二段开始逐段向前推进 for k in range(len(stages) - 2, -1, -1): for u in stages[k]: best INF for v, w in edges.get(u, []): cand w cost[v] if cand best: best cand nxt[u] [v] # 发现更优清空重记 elif cand best: nxt[u].append(v) # 并列最优追加 cost[u] best # 如果 best 仍是 INF说明 u 无法到达汇点保持不可达 return cost[stages[0][0]], nxt几个值得停下来看的点。第一nxt初始化成列表的列表而不是单个整数。原因在 2.2 已经说过这是为了保留并列最优解。如果你只想输出一条可以退化成单个整数代码少两行但功能就残缺了。第二判断条件的顺序很讲究。必须是先判小于、再判等于而且小于的时候要清空再追加。写反了、或者只写小于不写等于都会丢掉路径。这个逻辑跟 Dijkstra 里记录多条最短路是一模一样的套路。第三edges.get(u, [])用了默认空列表是为了处理某段顶点没有任何出边的边界情况。这种情况下 u 会保持 INF符合预期。4.3 正向DP把状态换成从源点到i的最短距离正向版本适合你想复用拓扑序、或者题目本身就要求从源点算起的场景def multistage_forward(n, stages, redges): redges[u] [(p, w), ...] 表示从 p 指向 u 且权为 w的入边 返回 (源点到汇点最短距离, 前驱列表) INF float(inf) dist [INF] * n prev [[] for _ in range(n)] src stages[0][0] dist[src] 0 for k in range(1, len(stages)): for v in stages[k]: best INF for p, w in redges.get(v, []): cand dist[p] w if cand best: best cand prev[v] [p] elif cand best: prev[v].append(p) dist[v] best return dist[stages[-1][0]], prev这份实现的时间复杂度同样是 O(V E)空间 O(V)。区别只在于递推方向不同以及记录的是前驱而不是后继。我个人更偏好反向版理由前面说过输出路径时不用 reverse直接顺着 nxt 打印就行读起来更符合从起点出发一路走到底的直觉。如果非要给性能排个序两种写法在同一张图上没有实质差异都是线性对边。所谓正向更快的说法在这个问题上不成立除非你的数据是流式给出的、必须边读边算那另说。4.4 输出全部最短路决策数组要从单值改成列表拿到 nxt 之后输出所有最短路的写法就是一个简单的 DFSdef enumerate_paths(nxt, src, sink, pathNone, resNone): if path is None: path, res [src], [] if src sink: res.append(list(path)) return res for nv in nxt[src]: path.append(nv) enumerate_paths(nxt, nv, sink, path, res) path.pop() # 回溯别忘了这一句 return res调用enumerate_paths(nxt, stages[0][0], stages[-1][0])就能把所有最优路径一次性列出来。上面那道例题会返回两条[1, 2, 7, 10, 12] [1, 3, 6, 10, 12]这里有个容易忽略的细节path.pop()必须写否则你会在同一条递归链上不断累积不同分支的顶点输出一堆杂乱的超长序列。这个坑不在算法本身而在回溯模板的书写习惯上写错了非常难查因为结果看起来像是对的路径但多了几个点。提示如果最短路数量可能爆炸某些图的并列决策能组合出指数级条数先跟出题人确认是否真的需要全部输出必要时改成只输出条数或输出字典序最小的一条。5. 我踩过的四个坑段序、INF、多解与孤立顶点5.1 顶点编号不等于段序最隐蔽的一类错最坑的一次经历是这样的题目给的图顶点编号是 1 到 12我下意识以为编号小的在前面的段于是循环写成for u in range(n-1, 0, -1)按编号从大到小推。跑出来的小样例看着没问题因为那个样例恰好编号顺序和段顺序一致换一个编号打乱的测试数据直接输出错误答案。顶点编号和阶段编号没有任何必然联系编号只是标识符段才是拓扑结构。正确做法是显式维护 stages 列表所有循环都基于 stages 展开绝不基于顶点编号做假设。如果题目只给图和边、不给段划分那就先做一次拓扑排序每个顶点的层级等于所有入边起点的最大层级加 1。这一步做完段划分就唯一确定了允许存在空段后续才能安心递推。我在写代码时习惯先把 stages 打印出来人工扫一眼每段的顶点数量和编号确认无误再往下写这两分钟能省掉半小时的 debug。5.2 INF加法与溢出Python之外的语言必须当心Python 里float(inf) 5还是inf太省心了所以我以前写 C 版本的作业时直接照搬INF 1e9然后写cand w cost[v]。当 cost[v] 是 1e9 的时候加上一个几万权值的边结果就是 1000000xxx仍然远大于任何合法距离不会误选。但如果 INF 取的是INT_MAX约 21 亿加上边权就直接溢出成负数然后这个负数比所有合法路径都小被 min 选中最后输出一个负的最短距离看上去像是图里有负权边。规避办法有两个一是 INF 取一个安全的大值比如10**9或者所有边权之和 1保证它加上任何边权都不会溢出二是在加法之前先判断if cost[v] INF: continue。我更推荐第二种逻辑上最干净也顺手处理了不可达顶点的问题。Java 里还可以用long存距离但治标不治本判断不可达才是正解。5.3 多解覆盖为什么你的程序只输出了一条路前面反复强调过这里再完整走一遍错误现场。假设你写的是if cand cost[u]: cost[u] cand nxt[u] v顶点 1 在计算时先遍历到走 2 得到 16写入 nxt[1] 2再遍历到走 3 也得到 16因为不满足小于所以不更新。最终 nxt[1] 只剩下 2输出的路径只有一条。如果你压根没意识到有第二条这个 bug 会一直潜伏到老师批改时才暴露。修复就是加一个elif cand best: nxt[u].append(v)并且把 nxt 从整数数组改成列表数组。改动很小但要求你在写第一版代码时就意识到多解这件事的存在。一个经验判断只要题目里出现输出所有最短路径或者最短路径有多少条决策数组就必须是列表。哪怕题目没明说养成列表的习惯也不吃亏顶多多两次 append。5.4 中间段有顶点不可达时该不该保留还有一种情况值得单独说某个中间段的顶点所有出边都通向死路比如它通向的顶点本身无法到达汇点那它的 cost 会一直是 INF。这时上一段在比较候选值时w INF显然不会被选为最优所以算法结果不受影响。但如果题目要求判断是否存在从源点到汇点的路径你就需要在最后检查 cost[源点] 是否仍是 INF。关于孤立顶点要不要从 stages 里剔除我的建议是保留但标记。剔除会让段结构错乱影响手动核对保留的话它自然会被 INF 排除代价只是多一次无效遍历。真正要小心的是某个段整体不可达的极端情况这时整段都是 INF属于题目本身无解应该在输出层给出明确提示而不是打印一个 inf 数字了事。6. 多段图DP的三种变形与选型边界6.1 求最长路径只有DAG才敢这么做一般图上的最长路径是 NP 难的因为要判断有没有正环但在多段图这种 DAG 上最长路径反而和最短路径是一对孪生兄弟只要把 min 换成 max 就完事longest[i] max{ w(i, j) longest[j] }边界依然是longest[汇点] 0。为什么这里可以随便取 max 而不用担心死循环还是因为无环——所有子问题都指向更靠后的段依赖关系严格递减永远推不回来。这一点在做资源最大化收益最大化这类题的时候特别有用比如项目排期里每个阶段选一个方案要求总收益最大本质就是多段图最长路径。不过要小心一点如果图里存在不可达的顶点max 版本会更危险因为 INF 参与 max 会直接污染结果。所以做最长路时遇到不可达顶点必须显式跳过不能参与比较。我通常会用一个单独的布尔数组标记可达性或者干脆把不可达顶点的值设成-INF再取 max。6.2 最短路径计数与第k短路在决策收集的基础上路径条数就是一个很自然的扩展设cnt[i]表示从 i 出发到汇点的最短路径条数则cnt[i] sum{ cnt[j] } 对所有满足 w(i,j) cost[j] cost[i] 的 j边界cnt[汇点] 1。这样一遍 DP 下来cnt[源点]就是所有最短路的条数不需要真的把每条路径都展开避免了指数级枚举。这个技巧在笔试里挺常见遇到最短路径有多少条直接上计数 DP比 DFS 枚举稳得多。至于第 k 短路做法就复杂一些了通常要维护每个顶点的 k 个候选值也就是把 cost 从标量升维成大小为 k 的小根堆逐段合并。多段图的结构能把它压到 O(k·(VE)·log k) 左右比一般的 Yen 算法友善不少。这块属于进阶内容期末题基本不会考但了解一下思路没坏处。6.3 什么时候该放弃多段图DP改用通用最短路用顺了这个套路之后容易产生什么都想套多段图的冲动。以下三种情况要果断换方案情形特征推荐方案存在同段之间的边边起点终点段号相同把同段合并后重排拓扑序或直接用通用最短路存在权重为负的边边权可能取负值先拓扑排序再用 DAG 最短路仍可 DP但顺序必须严格拓扑图中有环无法给出段划分Dijkstra非负权或 Bellman-Ford / SPFA简单总结成一句话多段图 DP 的核心竞争力来自无环 分段这两个结构性质一旦结构被破坏就得回到通用最短路工具。反过来说只要你确认了这两个性质就别去堆优化了一段双层循环就是最优解复杂度 O(VE)比朴素 Dijkstra 的 O(V²) 还快。再补一个实际经验很多在线判题系统会给出顶点数上限比如 n ≤ 1000、m ≤ 10000。看到这个量级如果你的代码是 O(V²) 的矩阵遍历勉强能过但很悬如果按段遍历邻接表跑起来连时间都感知不到。所以即使题目名字里写着动态规划也别忘了把数据结构选对这两件事从来不是分开的。我在实际做题和教学里发现这道题真正难的地方从来不是递推公式——那个公式看一遍就记住了——而是阶段划分的正确性、决策数组的多解处理、以及不可达状态的边界判定这三件事。公式所有人都能默写能把边界写干净、把并列解一个不漏地吐出来的人才是真正把这道题吃透了。下次再遇到多段图最短路径先别急着敲代码画个表把 stages 列出来按段倒着填一遍剩下的就只是翻译工作。