算法综合：从问题建模到可靠实现

从业务句子得到可验证问题

设一个区域有仓库、医院和道路。用户说“尽快把物资送到医院”，这还不是算法问题：是求一辆车到一个医院的最短时间，还是一辆车访问全部医院的路线？道路时间是否随方向不同，能否为负，封路如何表示，相同时间时怎样稳定选择？单源最短路和访问全部站点的巡回问题输出不同，复杂度也可能相差巨大，不能因为都出现“路线”就套同一算法。

本章固定如下契约：输入为有限有向图 $G=(V,E)$、源点 $s$ 和目标点 $t$；每条边 $(u,v,w)$ 表示从 $u$ 到 $v$ 的预计分钟数，要求 $w\ge0$。输出是从 $s$ 到 $t$ 的最小总时间及一条达到该时间的路径。若 $s$ 或 $t$ 不存在，输入无效；若目标不可达，返回明确的“不可达”状态而不是一个巨大伪距离；若存在平行边，均保留并由松弛自然选择较小者。输入规模用 $|V|$ 与 $|E|$ 表示，不能只写一个含义不明的 $n$。

模型必须说明目标函数。这里各段时间相加，目标是使和最小；它不包含车辆容量、时间窗或同时服务多个医院。增加这些约束会改变状态和可行解集合，甚至改变问题难度。算法评审的第一问不是“用了什么高级结构”，而是“返回值是否恰好回答了所建模的问题”。

表示选择就是不变量选择

地点的外部字符串标识先通过散列表映射到稳定内部编号；散列表维护“一种标识对应一个节点”的不变量。图用邻接表保存：对每个 $u$，adj[u] 只含起点为 $u$ 的合法边，终点编号属于节点范围，权重是有限非负数。构建阶段负责拒绝缺失节点、非数值权或负权，算法主体便可依赖这些条件，而不必在每次松弛时猜测数据是否有效。

Dijkstra 实现还维护距离数组 dist、前驱数组 pred、已确定集合 $S$ 和最小堆。初始化 $dist[s]=0$，其他为无穷；pred[v] 只在严格改善距离时更新。堆可以保留旧条目，但弹出 (d,u) 时若 $d\ne dist[u]$ 就跳过。这个“惰性删除”策略避免实现复杂的减键操作，其代价是堆中可能暂存多个同一节点条目；正确性依赖跳过过期项，而不是依赖堆内永远无重复。

前驱也有不变量：若 pred[v]=u，则存在边 $(u,v)$，且更新时满足 $dist[v]=dist[u]+w(u,v)$。目标确定后沿前驱反向追踪，必须最终到达源点；不可达节点没有前驱。若代码在相等距离时也随意互改前驱，零权环可能破坏路径恢复，因此平局规则应稳定且不得制造前驱环。

正确性：循环不变量连接代码与结论

终止性与部分正确性应分别说明。有限图上，每个有效松弛只产生有限次堆条目；每次循环弹出一个条目，因此循环终止。部分正确性的核心不变量是：每当节点 $u$ 以当前最小距离被加入 $S$，dist[u] 等于从源点到 $u$ 的真实最短距离；对尚未确定的节点，dist[v] 是目前找到的、内部节点都在 $S$ 中的路径的最小长度。

初始化时 $S$ 为空，源点的零长度路径是已知候选，其他节点无候选，不变量成立。保持步骤中，设堆顶当前节点为 $u$。若存在更短的源到 $u$ 路径，沿该路径找第一条从 $S$ 离开的边 $(x,y)$。由于边权非负，到 $y$ 的路径前缀不会长于到 $u$ 的整条路径；处理 $x$ 时已经松弛 $(x,y)$，于是 $y$ 的候选距离应小于 dist[u]，与 $u$ 是最小堆顶矛盾。故把 $u$ 确定是安全的。随后松弛 $u$ 的出边，恢复尚未确定节点的候选路径不变量。

这也是归纳证明：基例是源点，归纳步是每次安全加入一个节点。非负权不是装饰性前提，而是“路径继续延伸不会变短”的关键。算法在 $t$ 被确定时可提前停止，因为其距离已经最终；仅在 $t$ 第一次被发现时停止则错误，后来可能有更短候选。

复杂度必须绑定结构与操作

邻接表加二叉最小堆时，每条边至多触发一次成功改善并压堆，弹出次数与压入次数同阶，时间为 $O((|V|+|E|)\log|V|)$，空间为 $O(|V|+|E|)$，其中还包括图本身。若图连通且边数至少与节点数同阶，常简写为 $O(|E|\log|V|)$，但报告中保留完整式更清楚。数组扫描选择最小未确定节点的版本是 $O(|V|^2)$；在稠密图中它可能因连续内存和较小常数更快，渐近式不是唯一工程指标。

若所有边权都相等，队列 BFS 以 $O(|V|+|E|)$ 得到最少边路径，堆反而多余。若允许负权但不存在可达负环，可用 Bellman–Ford：令 $D_k(v)$ 表示最多使用 $k$ 条边到达 $v$ 的最小成本，递推考察最后一条边；连续做至多 $|V|-1$ 轮松弛，时间 $O(|V||E|)$。它体现动态规划而非 Dijkstra 的贪心确定。若第 $|V|$ 轮仍改善，存在可达负环，最小值可能无有限下界，应返回不同于“不可达”的失败状态。

分治也不是必须出现在每个解里。批量道路更新可先分段排序再归并，或在离线查询中分治时间区间；但单次非负最短路的关键结构是贪心安全性。范式是解释依赖关系的工具，不是为了凑齐术语而把一个自然循环硬拆成递归。

从需求规模到方案边界

一次查询、重复同源查询和大量任意点对查询是不同工作负载。重复同源查询可缓存一棵最短路径树，但道路更新后缓存需失效；大量源点查询可能考虑预处理，却要把预处理时间和存储一起计入。动态图中“每次更新后从头计算”是正确基线，是否需要增量算法应由更新频率、延迟预算和图规模决定，而不是先假设复杂结构必然更快。

数值类型也属于复杂度与正确性契约。若边权和路径长度可能超过整数上限，加法溢出会把大正数变成负数，破坏非负权证明。无穷哨兵参与加法前必须先判断可达，或使用能安全表示上界的类型。浮点权重则需定义比较容差与平局行为；不能一边证明精确次序，一边在实现中用不稳定近似比较。

测试是寻找证明前提被破坏的输入

示例测试只能说明几个点正确。更强的测试从契约和不变量生成：单节点且 $s=t$ 应返回零长度空边路径；目标不可达要返回状态而不是伪造路径；零权边、平行边、自环和多个等长最短路要有稳定行为；负权必须在入口被拒绝。大型权值测试检查溢出，旧堆条目测试检查惰性删除，乱序节点标识测试检查映射不依赖输入顺序。

性质测试可在随机小型非负图上验证：输出路径中的每条边真实存在，路径权和等于报告距离；算法结束后每条边满足 $dist[v]\le dist[u]+w(u,v)$；所有可达节点的前驱链最终到源点。还可用较慢但独立的 Bellman–Ford 与 Dijkstra 交叉核对。独立实现比复制同一松弛函数更有价值，因为共享错误不会互相揭示。

反例应尽量小。发现某启发式失败后，删除无关节点和边，直到再删一步错误就消失；这样的最小反例能直接指出缺失前提。测试失败不是“再加一个特殊分支”的自动许可，应先判断模型、证明还是实现哪一层出错。

一份可复核的交付清单

完整算法说明至少包含：问题与非目标、输入编码和规模、前置条件、输出及失败状态、数据结构及不变量、终止性、正确性证明、时间与空间、适用边界、替代方案和反例测试。代码中的入口校验应与证明前提一致，性能测试的图规模与稠密度应与复杂度参数一致，路径结果应带可独立核对的节点序列。

当需求变化时，从合同重新推导，而不是局部替换函数名。把“单源到单目标”改为“访问全部医院”，把静态非负时间改为可变负成本，或要求在每次封路后毫秒级响应，都可能需要新的状态空间和算法。综合能力不是记住最多算法，而是知道哪条结论依赖哪项前提，并能用证明和测试把选择边界公开给下一位维护者。

练习

关系与资源

• 序列、树与优先队列
• 散列表与图表示
• 分治与贪心策略
• 动态规划与图算法
• 复杂度与可计算性

MIT OpenCourseWare 6.006 用于核对数据结构、图表示、最短路、贪心正确性和复杂度分析的基础口径。本文把这些知识放入同一真实问题流程，重点是让模型、证明、实现和测试使用相同前提。

MIT《Mathematics for Computer Science》在本章用于支撑“算法正确性必须由离散结构上的论证保证”这一主张：图与关系给出配送网络的数学对象，归纳法和循环不变量解释最短路为何保持已确定距离，而渐近记号则把实现成本与输入规模联系起来。这些内容共同限定了综合案例中从问题合同到正确性证明的推理链。