一、起源:两类带权图的优化需求
图由顶点集合与连接顶点的边集合构成,边可以携带代价(长度、时延、费用、权重)。一旦边上有了数值,"选择哪些边"就从一个结构问题变成了优化问题。本文讨论两类最基本的优化问题,它们的区别在于优化的目标范围:一类只关心两个顶点之间的代价,另一类关心连接全部顶点的总代价。
1.1 从一点到另一点的最小代价问题
同一个需求在多个领域反复出现,形式一致而名称不同。
网络路由与选路。 数据包从源主机到达目的主机,中间要经过若干路由器。每条链路的转发代价不同,可以表示为跳数、带宽倒数、时延或链路开销。路由器需要为报文选择总代价最小的转发路径。路由表的条目由"目的网段 / 下一跳 / 出接口 / 度量(metric)"构成,其中度量正是边权的体现;协议运行在拓扑之上,反复计算到各目的网段的最小度量路径,把结果写进转发表。路由表的构成与最长前缀匹配的匹配规则见 linux: 网络管理 中网络层与路由表一节。
地图导航与路径规划。 路网是一张带权图,边的权重是通行时间或里程;导航需要给出从起点到终点的最少耗时路线。与抽象图不同的是,路网中的顶点带有地理坐标,这一额外信息可以被算法利用来加速搜索(2.5 节的启发式搜索)。
任务代价与状态转移。 依赖关系、剧本推进、状态机迁移都可以建模为带权有向图。把每个状态看作顶点、每次转移的代价看作边权,问题就成为"从初始状态到目标状态的最小代价",其解既给出最小代价,也给出达成该代价的转移序列。
这些场景的共同结构是给定源与目标,最小化路径上边权之和。若源固定而目标可以有多个,就得到单源最短路径问题;若需要任意两点之间的代价,就得到多源或全源问题。这两类问题的边界与算法选择是 2.1 节的主题。
1.2 连接所有节点且总代价最小的结构需求
另一类需求不关心某两个顶点之间怎么走,只关心把所有顶点连成一体需要付出多少总代价。连接方案本身的形态是一棵树:n 个顶点用 n−1 条边连通,恰好没有回路,也不浪费边。
布线与通信网络。 在若干建筑之间铺设光缆,使任意两处可以互通。可选的路由(边)及其长度(权)已知,需要选出一组边使全部节点连通且总长度最小。多铺一条边就多一份成本,因此最优方案必然是一棵树。
集群与机房互联。 机架内外的交换机与服务器需要用线缆互联,线缆长度与端口成本构成边权,目标是使整个集群连通且总物料成本最低。大规模集群的互联拓扑规划与此同构,只是边权换成了带宽成本或跨机架流量的代价。
其他抽象形式。 用最少的边使若干集合之间可达、用最低成本统一若干分立的网络,都归约为在同一张图上求一棵总权最小的生成树。
这类问题的共同结构是在连通图中选出 n−1 条边,使全体顶点连通且边权之和最小,即最小生成树(Minimum Spanning Tree,MST)。它与最短路径的关键区别是优化目标的范围:前者是全局的"总代价最小",后者是局部的"两点之间代价最小"。这一区别决定了二者不能用同一套算法,也不能互相替代(2.7.1 节)。
1.3 共同前提与本文边界
两类问题都建立在同一套图的基本表示之上。算法的输入是顶点的邻接关系与边的权值,通常用邻接矩阵(适合稠密图、随机访问快)或邻接表(适合稀疏图、空间与遍历代价低)存储。两种存储方式的取舍与数组、链表的一般性质一致,相关机制见 数组与链表。
本文的边界如下:
- 讨论带权图上的最短路径与最小生成树两类经典问题,包括它们的算法族、正确性依据与复杂度结论;
- 讨论算法的实现要点与工程选型,覆盖稀疏与稠密、单源与全源、静态与带启发信息等差异;
- 图的基本表示、遍历(深度优先、广度优先)与拓扑排序属于图算法的骨架,是按层或按顺序推进的基础,见 图的表示与遍历;其与本文算法在推进方式上的差异在 2.7.2 节说明。
需要先确立"代价如何度量"这一前提,这是后续所有算法复杂度结论的基础,相关口径见 复杂度与算法分析 中渐近记号与量级两节。
二、原理
2.1 问题分类与前提
在进入具体算法之前,需要把"最短路径"这一笼统说法拆开,因为不同前提下的问题是不同的,可用的算法也不同。算法选错的最常见原因不是实现有误,而是前提判断有误。
2.1.1 单源、多源与多对多
| 问题类型 | 需求 | 典型算法 | 复杂度 |
|---|---|---|---|
| 单源最短路(SSSP) | 一个源点到全部顶点的最短距离 | Dijkstra、Bellman-Ford、SPFA | 见 2.2 与 2.3 |
| 单源单汇 | 一个源到一个汇 | Dijkstra、A* | 同单源,A* 可显著加速 |
| 多源最短路 | 多个源点各自到全图 | 逐源运行单源算法,或加虚拟源 | 单源算法的倍数 |
| 全源最短路(APSP) | 任意两点之间的最短距离 | Floyd、逐源 Dijkstra | O(V³) 或 V·单源 |
| 多对多 | 多组指定的点对 | 按点对分别求解或用全源结果查表 | 取决于点对数量 |
几点说明:
- "多源"不等于"全源"。多源指有多个起点需要各自求出到全图(或到某集合)的距离,其解仍是若干组单源结果,可以用单源算法逐个源点运行;全源指需要任意两点这一完整矩阵,若图稠密,V 次单源算法的代价会超过 Floyd。
- 虚拟源技巧。若若干源点只需到达同一集合(例如"最近的配送中心"),可以引入一个到所有源点代价为 0 的虚拟源,一次单源求解即得到"任意点到最近源点"的距离,无需逐个源点运行。
- 单源最短路的结果包含一棵树。以源点为根,把每个顶点的最短路径上的前驱边连起来,得到的是一棵以源为根的有向树,称为最短路径树(shortest-path tree)。这棵树与最小生成树外形相似但含义不同:最短路径树保证"源到每个顶点的路径都是最短路径",而最小生成树保证"全体边的总权最小",二者一般不重合(2.7.1 节)。
2.1.2 边权的性质:非负、负权与负环
边权的取值范围决定了算法是否适用,这是选型中排在第一位的前提。
| 边权情形 | 含义 | 可用算法 |
|---|---|---|
| 全部非负 | 边权 ≥ 0,工程中的绝大多数场景 | Dijkstra、Bellman-Ford、Floyd |
| 存在负权但无负环 | 个别边权为负,图整体仍有意义 | Bellman-Ford、SPFA、Floyd |
| 存在负环 | 从某顶点出发绕一圈总权为负 | 检测并报告无解(负环上的最短路径无下界) |
| 全部为 1 | 无权或单位权 | 广度优先搜索即可 |
负环为什么使问题无解。 若存在一个从源点可达的环,其边权之和为负,则可以在到达目标前反复绕行该环,每绕一圈总代价都下降。绕行次数不受限制,代价值可以趋向负无穷,最短路径没有下界,"最短"这一概念失效。因此存在负环(且从源可达)时,问题的正确输出是"最短路径不存在",而不是某个有限数值。
负权的现实意义。 工程中负权并非纯粹的理论构造:汇率换算中买入与卖出的价差、物流中的补贴与返利、差分约束系统中"不小于"关系转成的负权边,都会出现负权。差分约束系统把一组形如 xⱼ − xᵢ ≤ w 的不等式转成有向边 i → j,权为 w,用 Bellman-Ford 判断可行性并求解,是负权算法的主要应用之一。
2.1.3 稠密图与稀疏图的差异
图的规模用顶点数 V 与边数 E 描述,二者的关系决定实现选择:
| 类型 | 边数范围 | 存储倾向 | 算法倾向 |
|---|---|---|---|
| 稀疏图 | E 与 V 同阶(E = O(V)) | 邻接表 | 基于优先级/堆的算法、Kruskal |
| 稠密图 | E 接近 V² | 邻接矩阵 | 朴素 O(V²) 实现、Floyd |
判据是复杂度表达式中的 V 与 E 哪一个占主导。Dijkstra 用二叉堆的代价是 O((V+E) log V),在稀疏图上退化为 O(V log V),在稠密图上为 O(V² log V),反而不如朴素实现的 O(V²)。因此"堆实现一定更快"是错误经验:稠密图应回退到线性扫描版本。这一现象与"小规模下插入排序胜过归并排序"同源,理论上界与实际快慢的差异口径见 复杂度与算法分析 中理论与实测的差异一节。
2.1.4 无向与有向
- 无向图的边可以双向通行,等价于两条方向相反、权相同的边。
- 有向图的边有方向,只沿边的指向通行。路由、依赖关系、状态转移都是有向的。
两处容易出错的地方:
- 无向图的负权边必然产生负环。一条权为负的无向边,来回走一次(u→v→u)即构成总权为负的环,因此无向图中出现负权边时,最短路径问题直接无解。这一结论把负权场景限制在有向图上。
- 最小生成树算法主要针对无向图。生成树要求"连通所有顶点",有向图中的对应概念是"有向生成树"(从根出发可达所有顶点),其算法不同(如最小树形图/朱刘算法)。把 Prim 或 Kruskal 直接用于有向图是常见误用(3.8 节)。
2.1.5 最短路与最长路
最短路径与最长路径在计算难度上并不对称。
- 最长路在一般图上不可行。若最长路问题允许负权(或等价地把权取反求最短),那么一条负环会让"最长"没有上界;即便限制非负权,求任意两点间最长简单路径与哈密顿路径问题相关,属于 NP 困难,不存在多项式算法。因此一般图上不讨论"最长路"这一通用问题。
- 有向无环图(DAG)上的最长路是可行的。无环这一条件排除了环的干扰,可以按拓扑序做一次线性递推,代价 O(V+E)。关键路径分析(项目管理中的最长耗时链)正是 DAG 最长路的应用。
| 问题 | 一般图 | DAG |
|---|---|---|
| 最短路径 | 多项式可解 | O(V+E)(按拓扑序松弛) |
| 最长路径 | NP 困难 | O(V+E)(按拓扑序松弛,权取负或直接取 max) |
这一对照说明:"把权取负再求最短"只在不存在负环时才合法,而 DAG 恰好保证了无环,因此是最长路少数可解的场景之一。
2.2 Dijkstra:贪心逐步确定
Dijkstra 算法解决非负边权的单源最短路径问题。它的思路是把顶点分成"已确定"与"未确定"两部分,每一轮从未确定集合中取出当前距离最小的顶点,宣布它的最短距离已定,再用它去更新邻居。
2.2.1 贪心选择
初始化时只有源点的距离为 0,其余顶点距离为无穷大。算法循环执行:
重复直到所有顶点都已确定:
1. 从未确定顶点中取出距离最小的顶点 u ← 贪心选择
2. 把 u 标记为已确定
3. 对 u 的每条出边 (u, v, w):
若 dist[u] + w < dist[v]: ← 松弛
dist[v] = dist[u] + w
记录 v 的前驱为 u
"贪心"体现在第 1 步:总是挑当前距离最小的那个顶点,不再回退。与背包、找零等贪心问题不同,这里的贪心选择可以被证明是正确的(2.2.3 节)。
2.2.2 松弛操作
松弛(relaxation) 是全部最短路算法的核心动作,含义是:若经由当前顶点可以更省地到达某个邻居,就更新该邻居的距离。
松弛边 (u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
直觉上,dist[v] 记录的是"目前已知的从源点到 v 的最小代价",松弛就是拿一条新路径去挑战这个记录。每条边在算法过程中可能被多次考察,只要它的一端被确定为当前最优,就会触发一次松弛尝试。
松弛的正确性依赖一条基础性质:最短路径的子路径也是最短路径(最优子结构)。因此到 v 的最短路径如果经过 u,那么该路径在 u 之前的部分必然就是到 u 的最短路径,用 dist[u] 加上边权 (u,v) 即得到经过 u 到达 v 的最小代价,无需重新展开整条路径。
2.2.3 正确性依赖非负边权的直觉解释
Dijkstra 的正确性可以归结为一个不变式:被取出并确定的顶点,其距离此后不会再被改进。
当取出距离最小的未确定顶点 u 时,其距离 dist[u] 已是最终值。理由是:任何一条从源点到 u 的、尚未被考虑的路径,必须在某个已确定顶点处离开已确定集合,再经由某个未确定顶点 x 进入。由于 u 是当前未确定顶点中距离最小的,有 dist[x] ≥ dist[u];又因为边权非负,沿该路径从 x 走到 u 只会让代价不减,因此这条路径的代价 ≥ dist[x] ≥ dist[u],不可能更优。
非负这一条件在其中起的作用是关键的一步:只有边权非负,才能保证"从更远的中间顶点继续走不会反而变近"。一旦允许负权,"经过更远的顶点再走一条负权边回到 u"就可能比 dist[u] 更省,u 的距离在取出后仍可能被改进,贪心选择的前提被破坏,算法给出错误结果(2.2.5 节)。
2.2.4 优先队列实现与复杂度
第 1 步的"取出距离最小的未确定顶点"正是优先队列的语义:顶点作为元素,当前距离作为关键字,反复取出最小值。这一步的结构决定了算法复杂度。
| 第 1 步的实现 | 取最小 | 单次松弛的调整 | 总复杂度 |
|---|---|---|---|
| 线性扫描全部未确定顶点 | O(V) | O(1) | O(V² + E) = O(V²) |
| 二叉堆 | O(log V) | O(log V) | O((V+E) log V) |
| d 叉堆 | O(log_d V) | O(log_d V) | 常数改进 |
| 斐波那契堆 | O(log V),均摊 | decrease-key 均摊 O(1) | O(E + V log V) |
几点说明:
- 二项的关键差别在减键(decrease-key)。用二叉堆时,每成功松弛一条边需要把该顶点的关键字改小,代价 O(log V),松弛最多发生 E 次,因此总复杂度 O((V+E) log V)。斐波那契堆把减键降为均摊 O(1),于是 E 次松弛的总代价降为 O(E),只剩 V 次取最小的 O(V log V),得到 O(E + V log V)。在稠密图(E 接近 V²)上,这一改进把界从 O(V² log V) 拉回到 O(V²) 量级。各类优先队列的操作代价对照见 堆与优先队列 中图算法中的优先队列一节。
- 标准库通常不提供减键接口。实现上改用惰性删除:不修改堆中的旧记录,而是插入一条更优的新记录;取出时校验该顶点是否已确定,已确定则丢弃并继续取下一个(3.1 节)。这一做法的复杂度与二叉堆减键同阶(均摊意义下),代价是堆中元素数可达 O(E) 而非 O(V)。
- 朴素实现的价值。V 较小(数百以内)且图稠密时,O(V²) 的线性扫描因缓存友好、无结构调整,实测常快于堆实现。斐波那契堆的理论界最优,但常数因子大、访问模式跳跃,实践中通常不如二叉堆或 d 叉堆,主要用于理论分析。
2.2.5 为什么不能处理负权
用一个具体例子说明 Dijkstra 在负权下的失效。
图:A → B 权 1,A → C 权 2,C → B 权 −2
Dijkstra 过程(源点 A):
初始 dist: A=0, B=∞, C=∞
取出 A(最小),标记确定,松弛:dist[B]=1, dist[C]=2
未确定集合为 {B(1), C(2)},取出最小的 B(距离 1),标记确定
B 无出边,结束
结果 dist[B] = 1
实际最短路径:A → C → B,代价 2 + (−2) = 0
错误原因:B 在距离为 1 时被取出并确定,但之后经过 C 的路径把 B 的距离
降到 0;Dijkstra 不会回头修改已确定的顶点。
失效的根源在于 2.2.3 节的论证被破坏:存在边权为负的边时,"从更远的顶点绕行再返回,代价可能更小"。因此:
- 处理负权应改用 Bellman-Ford 或 SPFA(2.3 节),或对全源问题使用 Floyd(2.4 节);
- 存在负环时无解,需要先检测(2.1.2 节);
- 若负权边数量极少,可以在保证不产生负环的前提下做变换,但一般不建议在具备负权的场景下使用 Dijkstra。
2.3 Bellman-Ford:逐轮松弛与负环检测
Bellman-Ford 放弃"选出最近顶点"这一贪心策略,改用最朴素的逐轮松弛,从而摆脱对边权非负的依赖,并顺带获得负环检测能力。
2.3.1 逐轮松弛与最多 n−1 轮的依据
算法流程:
初始化 dist[源] = 0,其余为 ∞
重复 V − 1 轮:
对图中的每一条边 (u, v, w):
若 dist[u] + w < dist[v]:
dist[v] = dist[u] + w
为什么是 V−1 轮。 一条最短路径最多包含 V−1 条边:路径上不能重复顶点(重复即出现环,而负环使问题无解、非负环可以去掉),因此简单路径至多经过 V 个顶点、V−1 条边。第 k 轮结束时,所有"至多使用 k 条边"的最短路径都已求出。经过 V−1 轮,所有可能的最短路径都被覆盖,结论收敛。
这一依据可以这样理解:每完成一轮,"沿最短路径还能走几步才到达"的信息就向前推进一层,类似按边的条数做逐层扩散。广度优先搜索在无权图上按跳数扩散,一次遍历即可,是因为那里"每层的代价相同";带权图上各边代价不同,无法按层一次到位,只能反复扫描所有边,直到没有更新。
2.3.2 负环检测方法
在 V−1 轮之后,再执行一轮扫描:如果仍有边可以松弛(dist[u] + w < dist[v]),说明存在一条使用 ≥ V 条边的更短路径,该路径必然含有环,且这个环的总权为负。
执行第 V 轮松弛:
若存在边 (u, v, w) 使 dist[u] + w < dist[v]:
存在从源点可达的负环,最短路径无解
判定条件是"能否被再次松弛",而不是"dist 中是否出现负值"。负权边的存在本身不构成负环,只有"绕一圈总和为负"才是负环。
需要区分两种可达性:
- 从源点可达的负环才会破坏最短路径的计算,用上述第 V 轮检测;
- 从源点不可达的负环不影响单源结果,但会使 Floyd 判定全图负环(2.4.4 节)。
2.3.3 SPFA 的队列优化与其局限
Bellman-Ford 每轮扫描全部边,其中大量松弛尝试是无效的(端点距离未变时不可能松弛成功)。SPFA(Shortest Path Faster Algorithm) 用队列只保留"距离刚刚变小、值得继续传播"的顶点:
dist[源] = 0,源入队
当队列非空:
取出队首 u
对 u 的每条出边 (u, v, w):
若 dist[u] + w < dist[v]:
dist[v] = dist[u] + w
若 v 不在队列中:把 v 入队
- 本质:SPFA 是 Bellman-Ford 的队列实现,每一轮只处理"上一轮发生了更新的顶点",把无效扫描去掉,属于同一种逐轮松弛思路的加速形式。
- 平均表现好,最坏界差。SPFA 的平均复杂度常被描述为 O(kE)(k 为每个顶点平均入队次数,通常很小),但最坏复杂度是 O(V·E)。存在刻意构造的网格图与链式图使其退化到最坏界,因此不应把 O(kE) 当作保证。
- 负环检测的写法。用一个计数数组记录每个顶点的入队次数:若某顶点入队次数达到 V,说明它参与了至少 V 条边的路径更新,存在可达负环。另一种等价写法是记录"最短路径经过的边数",超过 V−1 即判定负环。
- 队列替换为栈或双端队列可以改变处理顺序,得到不同常数与不同实测表现(如 SLF 优化:入队时与队首比较,更小则插入队首),但这些都只是启发式,不改变最坏界。
| 算法 | 时间复杂度 | 负权 | 负环检测 | 备注 |
|---|---|---|---|---|
| Bellman-Ford | O(V·E) | 支持 | 支持 | 每轮扫描全部边,界稳定 |
| SPFA | 平均 O(kE),最坏 O(V·E) | 支持 | 支持 | 实现简单,最坏界差 |
| Dijkstra(二叉堆) | O((V+E) log V) | 不支持 | 不支持 | 非负权下更快 |
选型结论:边权非负用 Dijkstra;存在负权用 Bellman-Ford 或 SPFA;不能接受最坏界退化时用 Bellman-Ford。
2.4 Floyd:多源最短路与动态规划视角
Floyd(Floyd-Warshall)算法解决全源最短路径问题,思路是动态规划,而不是从单源算法出发逐个源点求解。
2.4.1 动态规划的状态定义
状态定义为:
dp[k][i][j] = 从 i 到 j,只允许经过顶点集合 {1, 2, …, k} 作为中间点的最短距离
其中 k 从 0 递增。递推关系考虑"第 k 个顶点是否被用作中间点":
dp[k][i][j] = min( dp[k-1][i][j], ← 不使用顶点 k 作为中间点
dp[k-1][i][k] + dp[k-1][k][j] ) ← 用顶点 k 中转
- 第一项表示从 i 到 j 的最短路完全不经过 k;
- 第二项表示最短路经过 k,则把它拆成"i 到 k"与"k 到 j"两段,两段都只允许经过前 k−1 个顶点。
最终 dp[V][i][j] 即允许经过任意顶点作为中间点的最短距离,也就是所求。
2.4.2 三重循环与复杂度
状态是三维的,但有 V³ 个状态、每个状态 O(1) 转移,因此时间 O(V³)。空间上,dp[k] 只依赖 dp[k−1],可以用一个二维矩阵原地滚动,把空间降为 O(V²):
for k in 1..V:
for i in 1..V:
for j in 1..V:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
k 必须是最外层循环。 这是 Floyd 实现中最关键的一点。若把 k 放进内层,d[i][k] 与 d[k][j] 在计算 d[i][j] 时可能尚未完成对更小中间点集合的收敛,递推依赖被破坏,结果错误。原因在于原地滚动下,d[i][j] 在轮次 k 的值必须来自"只允许 {1..k−1} 作为中间点"的上一轮状态:当 k 在最外层时,本轮对 d[i][j] 的更新只会用到同为本轮值或上轮值的 d[i][k]、d[k][j],而这两者在同一个 k 下作为"端点"参与时恰好满足当前允许集合,因此原地更新仍然正确;换成其他循环顺序则无法保证。
2.4.3 路径还原
若只需距离矩阵,滚动数组足够。若还需要具体路径,需要额外的前驱矩阵(或后继矩阵):
next[i][j]记录"从 i 到 j 的最短路径上,i 的后继顶点";- 初始化
next[i][j] = j(当 i 与 j 之间有边);在d[i][j]被d[i][k] + d[k][j]改进时,同步令next[i][j] = next[i][k]。
还原路径时从 i 出发,反复取 next[cur][j] 直到到达 j。恢复一条路径的代价与路径长度成正比。
2.4.4 负环的判定
Floyd 同样可以检测负环,判据是正对角线:
若存在 i 使 d[i][i] < 0,则图中存在负环
含义是"从 i 回到 i 的路径代价为负",即存在经过 i 的负环。这与 Bellman-Ford 检测"从源可达的负环"不同:Floyd 检测的是图中所有顶点构成的负环(任意顶点可达性由矩阵自身给出)。若图中存在负环,则经过该环上任意顶点的最短路径都会被继续改进,Floyd 得到的矩阵对涉及负环的点对不再有意义。
2.4.5 与逐源 Dijkstra 的对比
| 方案 | 复杂度 | 适用 | 限制 |
|---|---|---|---|
| Floyd | O(V³),空间 O(V²) | V 较小、需要全源矩阵、稀疏稠密皆可 | 只适用于无负环图,大 V 时立方级代价过高 |
| 逐源 Dijkstra(二叉堆) | O(V·(V+E) log V) | 稀疏图、非负权、全源 | 不允许负权 |
| 逐源 Johnson | O(V·E + V² log V) | 稀疏图、含负权(先做重标号) | 实现复杂,需先检测负环 |
Johnson 算法的思路是"重标号 + 逐源 Dijkstra":先用一次 Bellman-Ford 求出势函数,把边权变换为非负而不改变最短路径的相对顺序,再对每个源运行 Dijkstra。它把稀疏图上的全源问题从 O(V³) 降到接近 O(V·E)。这是"负权算法与 Dijkstra 组合"的典型例子:只要能把负权消除(重标号),就能重新用上更快的非负权算法。
2.5 A* 与启发式搜索
Dijkstra 在搜索时对各个方向一视同仁,只按"从源点出发的代价"扩展,因此会均匀地向外铺开,直到触及目标。若已知目标的大致方位,这种均匀扩展浪费了大量无效搜索。A* 通过在排序键中加入"到目标还有多远"的估计,把搜索引向更有希望的方向。
2.5.1 估价函数
引入估价函数:
f(n) = g(n) + h(n)
g(n):从起点到 n 的实际代价(与 Dijkstra 的 dist 相同)
h(n):从 n 到目标的估计代价(启发函数,heuristic)
f(n):经过 n 的路径的估计总代价
优先队列按 f(n) 排序,而不是像 Dijkstra 那样按 g(n) 排序。h(n) 提供了"哪个方向更接近目标"的信息,从而优先扩展 f 更小的顶点。
2.5.2 与 Dijkstra 的关系
| 算法 | 排序键 | 效果 |
|---|---|---|
| Dijkstra | g(n)(起点代价) | 均匀扩展,保证最优,扩展点较多 |
| 贪心最佳优先搜索 | h(n)(估计剩余) | 直奔目标,速度快但可能不最优 |
| A*(h 可采纳) | f(n) = g(n) + h(n) | 兼顾方向与代价,保证最优且通常扩展更少 |
| A*(h 恒为 0) | g(n) | 退化为 Dijkstra |
A 是 Dijkstra 的推广*:当 h ≡ 0 时,f = g,A* 退化为 Dijkstra;h 越大,搜索越偏向目标。这一关系也解释了 A* 的正确性边界:h 提供的信息必须可靠,否则会把搜索引离最优解(2.5.3 节)。
2.5.3 启发函数的要求:可采纳与一致性
两个条件保证 A* 的结论正确且高效。
可采纳(admissible):对任意顶点 n,h(n) ≤ 从 n 到目标的真实最短距离。即启发函数从不高估剩余代价。
- 若 h 可采纳,A* 能保证找到最优解。直觉:高估会把某个非最优路径的 f 抬得过高,使算法误以为它比最优路径更贵,从而错过最优解;不高估则不会。
- 地图导航中,直线距离是一个可采纳的启发——两点间的实际路程不可能短于直线距离,因此直线距离从不高估剩余里程。
一致性(consistent,也称单调性):对任意边 (n, n') 及权 w,有 h(n) ≤ w + h(n')。即启发函数沿任意边下降的速度不超过边的实际权。
- 一致性比可采纳性更强:一致性蕴含可采纳性(从目标反向归纳可得 h(n) ≤ 真实距离)。
- 一致的 h 带来一条重要性质:每个顶点第一次被取出时其 g 值即为最终值,无需重新打开(reopen)已关闭的顶点。这与 Dijkstra 的性质同源——Dijkstra 正是 h ≡ 0(一致)的特例。
- 若 h 可采纳但不一致,A* 仍能给出最优解,但可能需要把已关闭的顶点重新放回队列再次扩展,实现更复杂、扩展次数更多。
| h 的性质 | 最优性 | 是否需重新打开已关闭顶点 | 典型场景 |
|---|---|---|---|
| h ≡ 0(一致) | 保证最优 | 不需要 | Dijkstra |
| 一致 | 保证最优 | 不需要 | A*,直线距离启发 |
| 可采纳但不一致 | 保证最优 | 可能需要 | 人工设计的启发 |
| 高估(不可采纳) | 不保证最优 | — | 追求速度的近似搜索 |
2.5.4 启发函数的设计与影响
启发函数的强度直接决定搜索效率。
- h 越接近真实剩余代价,扩展的顶点越少。当 h 恰等于真实代价时,搜索沿最优路径直行,几乎不扩展无关顶点。
- h 过于保守(远小于真实值)则接近 Dijkstra,保证最优但失去加速效果。
- h 高估(不可采纳)则可能不最优,但配合权重可以做成带权 A*(weighted A*):用 f = g + w·h(w > 1)放大启发,牺牲最优性换取速度,得到的是有界次优解。这是工程上在"必须最优"与"必须快"之间调比例的手段。
- 常见启发设计:网格地图用曼哈顿距离(四方向移动)或切比雪夫距离(八方向移动);路网用直线距离除以最高限速;状态空间搜索(八数码、华容道)用错位块数(可采纳但较弱)或曼哈顿距离之和(更强)。
2.5.5 适用场景
A* 的价值在于存在可靠的方向性启发信息:
- 地图导航与路径规划:顶点带地理坐标,直线距离是天然的强启发;
- 状态空间搜索:起点与目标之间的结构可估计剩余代价,如拼图类问题;
- 游戏寻路:网格地图上的曼哈顿/欧氏距离启发;
- 不适用:无坐标、无距离度量的抽象图(如纯依赖关系、社交网络),此时无可靠启发可用,只能退回 Dijkstra。
2.6 最小生成树:割性质与两种构造思路
最小生成树的目标是在连通无向图中选出总权最小的 n−1 条边,使全体顶点连通。它不指定源点、不关心点对之间的路径,只优化"连接全部顶点的总代价"。两个经典算法(Prim 与 Kruskal)分别对应两种构造思路,它们的正确性都可以由两条结构性定理保证。
2.6.1 割性质与环性质
割(cut) 是把顶点分成两个非空集合 S 与 V∖S 的划分。横跨割的边指一个端点在 S、另一个在 V∖S 的边。
割性质:对任意割,横跨该割的权最小的边,一定存在于某棵最小生成树中(若各边权互不相同,则存在于每一棵最小生成树中)。
直觉理解:一棵生成树必须至少有一条边横跨任意割,才能把 S 与 V∖S 连通。若某棵最小生成树用了横跨割的边 e 而非权最小的 e',可以用 e' 替换 e,得到总权不增仍连通的方案,说明最小生成树里可以包含 e'。
环性质:对任意环,该环上权最大的边一定不出现在任何最小生成树中(若权互不相同则可确定排除)。
直觉理解:生成树中不允许有环。若一棵生成树包含了某个环上权最大的边 e,把 e 去掉会使树分成两部分,而环上的其他边必然有一条可以重新连接这两部分,用这条更小的边替换 e 可得总权更小的方案,与最小性矛盾。
两条性质的对应关系:
| 性质 | 作用对象 | 结论 | 对应算法 |
|---|---|---|---|
| 割性质 | 割 | 横跨割的最小边必在某棵 MST 中 | Prim:选连接树与树外的最小边 |
| 环性质 | 环 | 环上最大边不在任何 MST 中 | Kruskal:按权从小到大取边,跳过成环的边 |
Prim 与 Kruskal 都可以看作"安全边定理"的具体实现:每一步都选一条保证属于某棵 MST 的边(安全边)加入,最终得到 MST。
2.6.2 Prim:逐步扩张
Prim 从一个起始顶点出发,把树逐步向外扩张:
从任意顶点 r 开始,标记 r 已加入树
重复直到全部顶点加入:
1. 在所有"一个端点在树内、另一个在树外"的边中,选权最小的边 (u, v)
2. 把 v 加入树
- 每轮选取的正是横跨"树内 / 树外"这一割的最小边,由割性质保证安全;
- 实现上,维护一个到树的最小距离数组,每轮取最小值(与 Dijkstra 的取最小操作同构,区别在于 Dijkstra 比较的是"源点到该点的累计距离",Prim 比较的是"该点到树中任意点的单边权");
- Prim 适用于连通图,若非连通,得到的是最小生成森林。
复杂度:
| 实现 | 取最小 | 总复杂度 | 适用 |
|---|---|---|---|
| 朴素数组扫描 | O(V) | O(V²) | 稠密图 |
| 二叉堆 + 邻接表 | O(log V) | O(E log V) | 稀疏图 |
| 斐波那契堆 | 摊还 O(log V) | O(E + V log V) | 理论最优 |
与 Dijkstra 一样,堆实现需要用惰性删除或索引堆来支持关键字修改(3.5 节)。稠密图上朴素 O(V²) 实现往往更快。
2.6.3 Kruskal:按边排序与并查集
Kruskal 换一个角度,从"边"出发:
1. 把全部边按权从小到大排序
2. 依次取出每条边 (u, v, w):
若 u 与 v 当前不在同一连通分量中: ← 加入后不会成环
把该边加入生成树
合并 u 与 v 所在的分量
3. 已加入 n−1 条边时结束
- "是否在同一分量中"的判断与"合并两个分量"正是**并查集(不相交集合)**的操作;
- 由环性质,环上最大边不会被选中;边按升序处理保证每次尝试的都是当前最小边,只要它不成环(由割性质知它安全)就被选中;
- Kruskal 天然支持非连通图,得到最小生成森林,不会因起点不存在而受阻。
并查集的两项优化(实现见 3.5.3 节):按秩(或按大小)合并使树高保持在 O(log n) 以内;路径压缩使查找接近 O(1)。两者同时使用时,n 次操作的总代价为 O(n·α(n)),α 为反阿克曼函数,在一切实际规模下不超过 4,工程上可按常数处理。这一摊还结论与其依赖的结构不变量见 复杂度与算法分析 中摊还与均摊实践一节;并查集的结构、路径压缩与按秩合并、以及带权变体的实现要点见 线段树与并查集。
复杂度:排序 O(E log E),并查集操作 O(E·α(V)),合计 O(E log E)。由于 E ≤ V²,log E 与 log V 同阶,常写作 O(E log V)。
2.6.4 复杂度对照与选择
| 算法 | 时间 | 空间 | 依赖结构 | 优势场景 |
|---|---|---|---|---|
| Prim(数组) | O(V²) | O(V²) 或 O(V) | 无(只需距离数组) | 稠密图 |
| Prim(二叉堆) | O(E log V) | O(V + E) | 优先队列 | 稀疏图 |
| Prim(斐波那契堆) | O(E + V log V) | O(V + E) | 斐波那契堆 | 理论最优 |
| Kruskal | O(E log E) | O(V + E) | 排序 + 并查集 | 稀疏图、非连通图、边较易枚举 |
选择依据:
- 稠密图(E 接近 V²)选 Prim 的数组实现。O(V²) 优于 O(E log V) = O(V² log V);且稠密图下数组的连续访问比堆的跳跃访问更适合缓存。
- 稀疏图(E 与 V 同阶)选 Kruskal。O(E log E) 与 O(E log V) 量级相近,而 Kruskal 只需一次排序加并查集,实现更简单,且不要求图连通。
- 边以列表形式给出时选 Kruskal,它不依赖邻接结构;需要从某个起点生长、或边难以一次性枚举时选 Prim。
- 理论上界不等于实测:小规模与稠密图上两者差异由常数项主导,结论应来自实测。
2.6.5 生成树不唯一与次小生成树
生成树不唯一。 当图中存在权值相等的边时,同一张图可能有多棵总权相同的最小生成树。例如一个正方形四个顶点、四条边权都为 1:任选其中三条边即得一棵 MST,共四棵。因此"求出最小生成树"通常指求出任一棵(总权确定),而不是求出唯一的边集。若需报告所有 MST 或判断某条边是否属于某棵 MST,需要额外的枚举或计数方法。
次小生成树。 在少数场景下,仅有一棵生成树不足以满足冗余性要求(例如需要一条备用链路)。次小生成树指总权严格大于或等于最小生成树、且在所有生成树中总权次小的那棵。常见求法是利用环性质:
- 先求一棵最小生成树 T;
- 对每条不在 T 中的边 (u, v, w),它加入 T 后形成一个唯一环,设环上除它之外的最大边权为 maxW;
- 用该边替换环上最大边,得到一棵总权为
sum(T) − maxW + w的新生成树; - 枚举所有非树边,取上述值最小者即次小生成树。
这一方法用到环性质(替换环上最大边),是"环性质用于判定某条边可否被替换"的直接应用。
2.7 与其他图问题的关系
2.7.1 最短路径与生成树的区别
两者都在带权图上做优化,但目标范围不同,因此不能互相替代。
| 维度 | 最短路径 | 最小生成树 |
|---|---|---|
| 优化目标 | 两点之间路径的边权之和最小 | 连接全部顶点的边权总和最小 |
| 结果形态 | 一棵以源为根的最短路径树(有向,依赖源点) | 一棵覆盖全体顶点的无向生成树 |
| 是否指定源 | 指定单源或点对 | 不指定源,全局 |
| 边权符号 | 非负或可含负权(无负环) | 一般要求非负;负权边在 MST 中需另行讨论 |
| 有向图 | 适用 | 不适用(有向图为最小树形图问题) |
| 计数 | 最短路径条数可多 | 生成树可多棵(权相等时) |
常见误区:把最小生成树上的路径当作最短路径。 一棵 MST 保证了"全体边的总权最小",但 MST 上两个顶点之间的路径未必是它们在原图中的最短路径。反之,由最短路径树也不保证总权最小。举一个典型例子:
顶点 A、B、C、D
边:A-B 权 1,B-C 权 1,C-D 权 1,A-D 权 5
最短路 A 到 D:A-B-C-D,代价 3
最小生成树:任选总权最小的 3 条连通边,例如 A-B(1)、B-C(1)、C-D(1),总权 3
(此例两者恰好一致)
反例:A-B 权 2,B-C 权 2,A-C 权 3,C-D 权 2
MST 取 A-B(2)、B-C(2)、C-D(2),总权 6
但 A 到 C 的最短路是 A-C 权 3(不经过 B),而 MST 上 A 到 C 的路径 A-B-C 代价为 4
结论:最短路关心"点对之间",MST 关心"全局连接成本",两者的最优解一般不同。
2.7.2 与拓扑排序、网络流的区别
拓扑排序处理的是有向无环图的顶点排序,使每条边都从较前的顶点指向较后的顶点。它与最短路径的关系有两点:
- DAG 上的最短路径可以按拓扑序线性求解,代价 O(V+E),比 Dijkstra 更快,且允许负权(无环即无负环);
- 拓扑排序是"按顺序"推进,最短路算法是"按代价"推进:前者只依赖边的方向,后者依赖边的权值与松弛。两者的推进依据不同,不能混用。
DAG 最短路与最长路的线性做法、关键路径分析属于拓扑排序的直接应用,其骨架(按层或按顺序遍历图)与最短路径算法共享"从已处理的顶点向外扩散"这一结构,深入的遍历实现不在此展开。
网络流处理的是流量分配问题:在容量约束下最大化从源到汇的流量,或求最小费用的流量方案。它与最短路径、生成树的区别在于:
| 问题 | 决策对象 | 约束 | 目标 |
|---|---|---|---|
| 最短路径 | 选一条路径经过哪些边 | 路径连通性 | 单条路径代价最小 |
| 最小生成树 | 选一组边连接全部顶点 | 连通、无环、n−1 条边 | 边权总和最小 |
| 网络流 | 给每条边分配流量 | 容量约束、流量守恒 | 流量最大或费用最小 |
三者中,网络流与最短路径有一个交叉点:最小费用最大流在增广时用最短路找"单位费用最小的增广路",此时最短路算法成为网络流的子过程。这说明不同图问题常以子过程的形式互相嵌套,算法族的边界不是绝对的;强连通分量、最大流与最小割、费用流与二分图匹配的算法族见 进阶图算法。
三、实现
3.1 Dijkstra 实现要点
3.1.1 距离数组与已确定标记
dist[v]保存当前已知的从源点到 v 的最小距离,初始化为无穷大、dist[src] = 0;done[v]标记顶点是否已被取出确定。不要用"是否在堆中"代替 done:惰性删除下同一顶点可能在堆中出现多次;- 前驱数组
prev[v]用于还原路径(把prev沿源点回溯)。
3.1.2 优先队列的惰性删除技巧
标准库优先队列不提供 decrease-key,因此采用惰性删除:不修改堆中旧记录,而是插入一条更优的新记录,取出时校验并跳过过期项。
入队:把 (新距离, 顶点) 作为一个新条目压入堆,不删除旧条目
取出:弹出堆顶 (d, u)
若 done[u] 为真:该条目已过期,直接跳过,继续取下一个
否则:标记 done[u] = true,以 d 作为 u 的最终距离,松弛其出边
- 正确性依赖一条规则:每个顶点第一次被取出时即为最终距离(由非负边权和贪心性质保证)后继的重复条目都会被
done拦下; - 代价:堆中条目数可达 O(E) 而非 O(V),空间从 O(V) 升到 O(E),但总复杂度仍是 O((V+E) log V);
- 比较的是距离而非顶点编号,因此堆元素通常是
(距离, 顶点)对。
3.1.3 完整实现(Java,邻接表 + 二叉堆)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Dijkstra {
/** 边:目标顶点与权值。 */
static class Edge {
final int to;
final long weight;
Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
/**
* 非负边权的单源最短路。
* @param n 顶点数,编号 0..n-1
* @param graph 邻接表
* @param src 源点
* @return 最短距离数组;不可达处为 Long.MAX_VALUE
*/
public static long[] shortestPaths(int n, List<List<Edge>> graph, int src) {
long[] dist = new long[n];
boolean[] done = new boolean[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
// 堆元素为 {距离, 顶点},按距离升序
PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
heap.offer(new long[]{0, src});
while (!heap.isEmpty()) {
long[] top = heap.poll();
long d = top[0];
int u = (int) top[1];
if (done[u]) { // 惰性删除:跳过过期条目
continue;
}
done[u] = true; // 第一次取出即最终确定
for (Edge e : graph.get(u)) {
long nd = d + e.weight;
if (nd < dist[e.to]) { // 松弛成功
dist[e.to] = nd;
heap.offer(new long[]{nd, e.to}); // 不修改旧条目,插入新条目
}
}
}
return dist;
}
}
要点核对:
- 距离用
long。int在路径较长或多段权值叠加时容易溢出;无穷大用Long.MAX_VALUE,且松弛前应确认dist[u]不是无穷大(不可达顶点不应参与松弛),或改用足够大的哨兵值如Long.MAX_VALUE / 4以避免加法溢出; if (done[u]) continue;是惰性删除的关键,漏掉它会把已确定顶点再次扩展,导致dist被错误覆盖或重复松弛;- 该实现在稠密图上(V 较小)可改为朴素 O(V²) 版本以利用缓存;
- 若要还原路径,追加
prev数组并在松弛成功时记录prev[e.to] = u。
各语言要点:
| 语言 | 优先队列 | 惰性删除写法 | 注意 |
|---|---|---|---|
| Java | PriorityQueue(小顶堆) | 弹出后检查 done | 元素用数组或 long 编码(d * n + v)避免对象开销 |
| C++ | std::priority_queue(大顶堆) | 存负距离或自定义比较器 | 默认大顶堆,需存 -d 或传 greater |
| Python | heapq(小顶堆) | 存 (d, u) 元组 | 元组比较会在距离相等时比较 u,需保证可比较 |
| Go | container/heap | 实现 Less 按距离排序 | 需实现五个方法 |
3.2 Bellman-Ford 与 SPFA 实现要点
3.2.1 松弛循环与提前退出
import java.util.Arrays;
/** 边列表形式;返回 null 表示存在从源点可达的负环。 */
public static long[] bellmanFord(int n, int[][] edges, int src) {
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE / 4); // 避免加法溢出
dist[src] = 0;
for (int round = 0; round < n - 1; round++) {
boolean updated = false;
for (int[] e : edges) { // e = {u, v, w}
int u = e[0], v = e[1], w = e[2];
if (dist[u] + w < dist[v]) { // 只从可达顶点松弛
dist[v] = dist[u] + w;
updated = true;
}
}
if (!updated) { // 提前退出:本轮已无更新,后续也不会变
break;
}
}
for (int[] e : edges) { // 第 n 轮:仍可松弛则存在可达负环
int u = e[0], v = e[1], w = e[2];
if (dist[u] + w < dist[v]) {
return null;
}
}
return dist;
}
要点:
- 提前退出。若某一轮没有任何更新,说明距离已收敛,可立即结束,平均情况下能省下大量轮次;
- 只从可达顶点松弛。
dist[u]为哨兵值(不可达)时,dist[u] + w仍接近哨兵,不应作为有效的候选。用Long.MAX_VALUE / 4之类的哨兵可以避免加法回绕成负数造成的错误更新; - 负环检测放在 n−1 轮之后,判据是"仍存在可松弛的边",而不是"是否存在负距离"。
3.2.2 SPFA 的最坏复杂度与使用注意
from collections import deque
def spfa(n, graph, src):
"""graph[u] = [(v, w), ...];返回 None 表示存在从源点可达的负环。"""
INF = float("inf")
dist = [INF] * n
dist[src] = 0
in_queue = [False] * n
enqueue_count = [0] * n # 入队次数,用于负环检测
q = deque([src])
in_queue[src] = True
enqueue_count[src] = 1
while q:
u = q.popleft()
in_queue[u] = False
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
enqueue_count[v] += 1
if enqueue_count[v] >= n: # 入队达到 n 次:存在可达负环
return None
q.append(v)
in_queue[v] = True
return dist
要点与风险:
- 最坏复杂度为 O(V·E)。存在专门构造的网格图与链式图使 SPFA 退化到最坏界。不应对 SPFA 的"平均很快"形成依赖,尤其是在无法控制输入形态的场景;
- 入队次数阈值用 V 而非 n 以外的值:某顶点入队达到 V 次,说明其最短路径经过的边数达到 V,必含环且为负环;
in_queue与enqueue_count含义不同:前者用于避免同一顶点在队列中重复出现,后者用于负环检测,两者都不能省略;- SLF/LLL 等优化只是启发式,改变的是处理顺序与常数,不改变最坏界;
- 若负环不可达,SPFA 不会触发阈值,返回的是正常结果;与 Bellman-Ford 一样,检测的是"从源可达"的负环。
3.3 Floyd 实现要点
3.3.1 三重循环顺序(k 必须在外层)
/** 全源最短路;INF 用足够大的哨兵避免加法溢出。 */
public static long[][] floyd(int n, long[][] w) {
long INF = Long.MAX_VALUE / 4;
long[][] d = new long[n][n];
for (int i = 0; i < n; i++) {
System.arraycopy(w[i], 0, d[i], 0, n);
d[i][i] = 0; // 自身到自身距离为 0
}
for (int k = 0; k < n; k++) { // k 必须在最外层
for (int i = 0; i < n; i++) {
if (d[i][k] == INF) { // 剪枝:i 到 k 不可达,无需再枚举 j
continue;
}
for (int j = 0; j < n; j++) {
long throughK = d[i][k] + d[k][j];
if (throughK < d[i][j]) {
d[i][j] = throughK;
}
}
}
}
return d;
}
要点:
- k 在最外层是正确性的前提(2.4.2 节)。写成 i 或 j 在外层、k 在内层是典型错误,结果会偏大或错误;
d[i][k] == INF剪枝可以跳过大量无效计算,稀疏图或不可达点较多时收益明显;- 哨兵值的选取:用
Long.MAX_VALUE / 4之类的值,使两次哨兵相加不会溢出成负数,从而不会被误判为更短路径。
3.3.2 路径还原的前驱矩阵
初始化:若 i 与 j 之间有边且 i ≠ j,令 next[i][j] = j;否则 next[i][j] = -1
转移: 当 d[i][j] 被 d[i][k] + d[k][j] 改进时,令 next[i][j] = next[i][k]
还原 i → j 的路径:
path = [i]
while i != j:
i = next[i][j]
if i == -1: 不可达,退出
path.append(i)
要点:next[i][j] 记录的是"i 的后继",因此转移时复制的是 next[i][k](i 到 k 的首跳),而不是 next[k][j]。
3.3.3 内存优化
| 版本 | 空间 | 说明 |
|---|---|---|
| 三维 dp[k][i][j] | O(V³) | 直接按状态定义写,逻辑最清晰,实际很少使用 |
| 二维滚动(原地) | O(V²) | k 在外层时原地更新仍正确,是最常用形式 |
| 需要路径还原 | O(V²) 额外 | 需要 next 矩阵与距离矩阵并存 |
原地滚动的正确性来自 2.4.2 节的说明:k 在最外层时,本轮用到的 d[i][k]、d[k][j] 恰好是允许集合下的正确值,因此无需保留上一轮的完整副本。
3.4 A* 实现要点
3.4.1 优先队列按估价排序与关闭集
import java.util.Arrays;
import java.util.PriorityQueue;
/**
* 网格上的 A*,0 表示可通行,1 表示障碍;四方向移动,代价为 1。
* 返回最短步数,不可达返回 -1。
*/
public static int aStar(int[][] grid, int[] start, int[] goal) {
int rows = grid.length, cols = grid[0].length;
int[][] g = new int[rows][cols];
for (int[] row : g) {
Arrays.fill(row, Integer.MAX_VALUE);
}
boolean[][] closed = new boolean[rows][cols];
int[] sr = {start[0]}, sc = {start[1]};
g[sr[0]][sc[0]] = 0;
PriorityQueue<int[]> open = new PriorityQueue<>(
(a, b) -> Integer.compare(a[0], b[0])); // 小顶堆,键为 f
open.offer(new int[]{manhattan(sr[0], sc[0], goal), sr[0], sc[0]});
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!open.isEmpty()) {
int[] cur = open.poll();
int r = cur[1], c = cur[2];
if (closed[r][c]) { // 惰性删除过期条目
continue;
}
if (r == goal[0] && c == goal[1]) {
return g[r][c];
}
closed[r][c] = true; // 关闭集:已确定,不再扩展
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
continue;
}
if (grid[nr][nc] == 1 || closed[nr][nc]) {
continue;
}
int ng = g[r][c] + 1;
if (ng < g[nr][nc]) { // 找到更优的 g
g[nr][nc] = ng;
int f = ng + manhattan(nr, nc, goal);
open.offer(new int[]{f, nr, nc}); // 入堆的键是 f,不是 g
}
}
}
return -1;
}
private static int manhattan(int r, int c, int[] goal) {
return Math.abs(r - goal[0]) + Math.abs(c - goal[1]);
}
要点:
- 堆的排序键必须是 f = g + h,而不是 g。写成 g 就退化为 Dijkstra,失去启发加速;
- 若 f 相等,可追加 g 作为次序键:优先扩展 g 更大(更深入)的顶点,可减少同 f 值的无效扩展,是一种常见的打破平局策略;
- 关闭集记录已确定不再扩展的顶点。启发函数一致时,顶点第一次被取出即可关闭(3.4.2 节);
- 四方向网格用曼哈顿距离、八方向用切比雪夫距离,都能保证不高估。
3.4.2 启发函数的要求与常见设计
- 可采纳性优先于速度:只要 h 可能高估,最优性即失去保证。工程上若要提速,宁可显式采用带权 A*(
f = g + w·h),也不要偷偷使用高估的 h; - 一致性保证关闭集安全:h 一致时无需重新打开已关闭顶点,实现简单且高效(2.5.3 节);
- h 的计算要廉价:h 每次扩展都要计算,若启发函数比边扩展本身还贵,加速会被抵消。应使用 O(1) 可算的度量(距离公式),而不是运行子搜索。
3.5 生成树实现要点
3.5.1 Prim 的优先队列版本
Prim 与 Dijkstra 的结构几乎相同,差别只在堆的键:
| 算法 | 堆中关键字 | 含义 |
|---|---|---|
| Dijkstra | dist[u] + w | 源点到 v 的累计代价 |
| Prim | w | 顶点 v 到当前树的单条边权(取最小) |
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
/** 稠密图友好的朴素 Prim:O(V²),返回 MST 总权;图不连通时返回部分森林的权。 */
public static long primDense(int n, long[][] w, long INF) {
boolean[] inTree = new boolean[n];
long[] minEdge = new long[n]; // 每个顶点到树的最小边权
Arrays.fill(minEdge, INF);
minEdge[0] = 0;
long total = 0;
for (int iter = 0; iter < n; iter++) {
int u = -1;
for (int v = 0; v < n; v++) { // 线性扫描找最小边
if (!inTree[v] && (u == -1 || minEdge[v] < minEdge[u])) {
u = v;
}
}
if (u == -1 || minEdge[u] == INF) {
break; // 图不连通
}
inTree[u] = true;
total += minEdge[u];
for (int v = 0; v < n; v++) { // 用 u 更新树外顶点的最小边
if (!inTree[v] && w[u][v] < minEdge[v]) {
minEdge[v] = w[u][v];
}
}
}
return total;
}
- 朴素版本用
minEdge数组代替优先队列,每轮 O(V) 找最小、O(V) 更新,合计 O(V²),稠密图上优于堆版本; - 稀疏图上改用堆 + 邻接表,得到 O(E log V),同样使用惰性删除(3.1.2 节)。
3.5.2 Kruskal 的排序与并查集
import java.util.Arrays;
/** 边按权升序排序后逐条尝试,用并查集判环;O(E log E)。 */
public static long kruskal(int n, int[][] edges) {
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); // {u, v, w}
DSU dsu = new DSU(n);
long total = 0;
int used = 0;
for (int[] e : edges) {
if (dsu.union(e[0], e[1])) { // 两端不在同一分量即可安全加入
total += e[2];
if (++used == n - 1) {
break; // 已选够 n-1 条边
}
}
}
return total; // used < n-1 表示图不连通(最小生成森林)
}
3.5.3 并查集与边的数据结构设计
并查集的两项优化:
/** 并查集:按大小合并 + 路径压缩,摊还每次近 O(α(n))。 */
class DSU {
private final int[] parent;
private final int[] size;
DSU(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径压缩(隔代压缩)
x = parent[x];
}
return x;
}
/** 合并成功返回 true,已在同一集合返回 false。 */
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) {
return false;
}
if (size[ra] < size[rb]) { // 小树挂到大树上
int t = ra;
ra = rb;
rb = t;
}
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
}
边的数据结构设计:
- Kruskal 需要按权排序的边列表,边用
(u, v, w)三元组表示最直接;若用邻接表,需要先展开成边列表,且无向图的每条边只需存一次(不应存成两条,否则重复处理不影响正确性但会多做一次查找); - Prim 需要按顶点访问其全部邻边,用邻接表更合适;无向图的每条边在邻接表中存成两条;
- 边权类型:多段权值累加时用
long,避免溢出; - 自环与重边:自环(u == v)在并查集中会被
find(u) == find(v)拦下,可安全忽略;重边(同一对顶点间多条边)在 Kruskal 中保留最小的一条即可,其余冗余。
3.6 复杂度与实测
3.6.1 各算法在稀疏与稠密图上的复杂度对照
| 算法 | 时间(一般) | 稀疏图(E≈V) | 稠密图(E≈V²) | 空间 | 负权 | 负环 |
|---|---|---|---|---|---|---|
| Dijkstra(朴素) | O(V²) | O(V²) | O(V²) | O(V) | 否 | 否 |
| Dijkstra(二叉堆) | O((V+E) log V) | O(V log V) | O(V² log V) | O(V+E) | 否 | 否 |
| Dijkstra(斐波那契堆) | O(E + V log V) | O(V log V) | O(V²) | O(V+E) | 否 | 否 |
| Bellman-Ford | O(V·E) | O(V²) | O(V³) | O(V) | 是 | 是 |
| SPFA | 平均 O(kE),最坏 O(V·E) | 常快 | 最坏 O(V³) | O(V) | 是 | 是 |
| Floyd | O(V³) | O(V³) | O(V³) | O(V²) | 是 | 是 |
| A* | 取决于 h | 通常远少于 Dijkstra | 通常远少于 Dijkstra | O(V) | 否 | 否 |
| Prim(数组) | O(V²) | O(V²) | O(V²) | O(V) | 视实现 | 不适用 |
| Prim(二叉堆) | O(E log V) | O(V log V) | O(V² log V) | O(V+E) | 视实现 | 不适用 |
| Kruskal | O(E log E) | O(V log V) | O(V² log V) | O(V+E) | 视实现 | 不适用 |
读数要点:
- Dijkstra 的堆实现只在稀疏图上优于朴素实现。稠密图(E 接近 V²)时
(V+E) log V与V² log V反而不如V²,此时应回退到朴素版本; - Floyd 的复杂度与 E 无关,稠密图上是自然选择,稀疏图上应改用逐源 Dijkstra 或 Johnson;
- Kruskal 的 O(E log E) 在稠密图上退化为 O(V² log V),此时 Prim 的 O(V²) 更优;
- 复杂度只是筛选器,相同量级下实际快慢由常数、缓存、实现细节决定。
3.6.2 实测与理论差异
- 手写计时在 JIT 环境下不可靠。预热不足、死代码消除、常量折叠都会使结果偏离真实值;比较 Dijkstra 的堆实现与朴素实现、比较 Prim 与 Kruskal 的交叉点,都应使用基准框架,相关陷阱与结果判读见 JMH 微基准测试。
- 缓存效应会改变实现排序。邻接矩阵是连续存储、随机访问快;邻接表的访问跳跃、缓存未命中多。小规模稠密图上朴素 O(V²) 实现常因缓存友好而胜出。
- 基准要控制变量:图密度(E/V 比例)、V 的规模、边权分布、是否连通、数据是否随机,都会影响结论。应至少覆盖"稀疏 + 小 V"与"稠密 + 小 V"两类用例,观察实测比值随规模变化的趋势。
- 堆元素的对象开销常被忽略。Java 中用
long[]作为堆元素会带来装箱与数组分配开销,把(距离, 顶点)编码为单个long(如d * V + v)可以显著降低开销。这类优化在基准中会被放大,需注意区分"算法差异"与"对象分配差异"。
3.7 应用案例
3.7.1 网络路由与选路策略
路由器运行的路由协议本质上是在拓扑图上反复求解最短路,并把结果写入转发表。
- 链路状态协议(如 OSPF):每个路由器获得全网拓扑(链路状态数据库),以自己为根运行 Dijkstra,得到到各网段的最短路径树,再据此生成转发表。这正是单源最短路径在工程中的标准用法。
- 距离向量协议(如 RIP):每个节点只与邻居交换"到各目的地的距离向量",反复更新,收敛到最短路。它与 Bellman-Ford 的逐轮松弛同构(2.3.1 节)。
- 选路的度量与策略:实际选路不只看跳数,还受带宽、链路开销、策略(如流量工程、等价多路径)影响。路由表的条目构成(目的网段 / 下一跳 / 出接口 / 度量)与最长前缀匹配的规则见 linux: 网络管理 中网络层与路由表一节。
- 环路问题:距离向量协议在链路故障时会遇到"计数到无穷"问题,工程上通过水平分割、毒性逆转、定义最大跳数等手段缓解,其根源正是"逐轮松弛在负权/无界情况下可能不收敛"这一理论性质在协议层面的体现。
3.7.2 地图导航与路径规划
- 基础方案是 Dijkstra 或 A*:路网是带权有向图,边权为通行时间;A* 用直线距离等可采纳启发大幅减少扩展顶点;
- 预处理加速:全网点对点查询频繁时,单次运行 Dijkstra 的成本过高,工程上使用层次化图、路网压缩、地标(landmark)等预处理技术,把查询降为毫秒级。这些方法的共同前提是"路网是静态或变化缓慢的",与 3.7.1 的动态路由形成对照;
- 多目标与约束:实际导航还需处理禁行、收费、多途经点等约束,属于带约束的最短路变体,通常通过状态扩展((顶点, 约束状态) 作为新顶点)转化为普通最短路。
3.7.3 集群与机房互联的拓扑规划
- 最小成本布线是 MST 的直接应用:机房内机架、交换机、服务器互联时,用最小生成树给出总线缆成本最低的连通方案(2.6 节);
- 冗余与次小生成树:生产网络不能只连一次,需要备用链路,次小生成树给出"在一棵最优连接的基础上,最小代价的替代方案"(2.6.5 节);实际设计中常在此基础上叠加环网(如生成树协议防止二层环路);
- 带宽与容量约束:真实集群互联的边权不只是线缆长度,还包括带宽成本与跨机架流量代价,权重的定义直接决定"最小"的含义。
3.7.4 任务依赖下的最短耗时估算
- 关键路径法(CPM):项目任务构成 DAG,顶点为任务、边为依赖、边权为任务耗时;整个项目的最短完成时间等于 DAG 上的最长路径(关键路径),因为必须等最长的那条依赖链全部完成。这与 2.1.5 节的 DAG 最长路一致;
- 计算方式:按拓扑序对 DAG 做一次线性递推,代价 O(V+E),同时得到每个任务的最早开始时间与总浮动时间;
- 与最短路的区别:这里求的是最长路径而非最短路径,且之所以可行,正是因为依赖关系构成 DAG 而非一般图(2.1.5 节)。
3.7.5 通信网络的最小成本布线
- 运营商骨干网与园区网:在待选链路集合中选一组连通全部节点且总成本最低的边,是 MST 的典型形态;链路成本可以按距离、租赁费用或建设复杂度定义;
- 与最短路的分工:布线优化关心"总成本最小"(MST),而选路优化关心"两个节点之间代价最小"(最短路)。同一张物理网络上,两者分别回答不同的规划问题(2.7.1 节);
- 非连通与分区:待建网络可能本就分为若干区域,此时求的是最小生成森林而非单棵 MST,Kruskal 天然支持这一情形(2.6.3 节)。
3.8 常见问题与排查
| 现象 | 可能原因 | 验证与处置 |
|---|---|---|
| Dijkstra 结果比真实最短路径偏大,且偏大的点均位于负权边之后 | 图中存在负权边,破坏了"取出即确定"的前提 | 检查边权是否有负值;改用 Bellman-Ford 或 SPFA;若为无向图,负权边直接导致负环,问题无解 |
| 距离出现负数或异常大的数值 | 距离类型为 int 且权值累加溢出;或初始值设为 Integer.MAX_VALUE 后相加回绕成负数 | 改用 long;无穷大用 Long.MAX_VALUE / 4 之类的哨兵,松弛前确认源点可达 |
| 多源场景结果不正确或耗时过长 | 直接对单个源运行、遗漏部分源点;或对稠密图逐源运行堆版 Dijkstra | 确认需要的是"多源"还是"全源";全源问题在稠密图用 Floyd,稀疏图用逐源 Dijkstra 或 Johnson(2.4.5 节) |
| 稠密图上 Dijkstra/Prim 比预期慢很多 | 误用堆实现,(V+E) log V 退化为 V² log V,不如朴素 O(V²) | 按 E/V 比例选择实现;稠密图回退到线性扫描版本(2.1.3 节) |
| 有向图上用 Prim/Kruskal 求"最小生成树"结果无意义 | 生成树针对无向图;有向图对应的是最小树形图,需要朱刘算法 | 确认图是有向还是无向;有向图改用最小树形图算法(2.1.4 节) |
| Kruskal 结果总权偏小或漏边 | 无向图把每条边存成两条重复处理;或未处理重边导致重复计数;或自环参与排序未被跳过 | 无向图每条边只存一次;自环在并查集中会被自然拦下;重边保留最小者即可 |
| 生成树算法返回的边数不足 n−1 | 图不连通;或并查集实现错误导致连通分量判断失效 | 检查图是否连通;验证并查集的 find 是否做了路径压缩、union 是否按秩/按大小合并(3.5.3 节) |
| Dijkstra 中某些顶点被重复扩展或距离被覆盖 | 惰性删除的过期条目检查缺失,已确定顶点被再次处理 | 弹出时先判断 done[u],为真则跳过;确认 done 在第一次取出时即置位(3.1.2 节) |
| SPFA 在部分输入上耗时暴增、接近超时 | SPFA 最坏复杂度为 O(V·E),存在刻意构造的退化输入 | 记录顶点入队次数与总松弛次数;输入形态不可控时改用 Bellman-Ford 或对边界做保护(3.2.2 节) |
| A* 结果不是最优路径 | 启发函数高估剩余代价,不满足可采纳性 | 校验 h(n) ≤ 真实剩余距离;地图用直线距离而非道路距离;若刻意提速改用带权 A* 并接受次优 |
| A* 扩展次数与 Dijkstra 相当、没有加速 | 启发函数恒为 0 或过于保守;或堆的排序键误用了 g 而非 f | 检查入堆的键是否为 f = g + h;选择信息量更强的启发(3.4.2 节) |
| Floyd 结果偏大,且差值随中间点增多而扩大 | 三重循环顺序错误,k 未放在最外层 | 调整为 for k → for i → for j;用已知小图手工推演验证(3.3.1 节) |
| Floyd 判定存在负环,但业务图不应有负环 | 图中确有负环;或"负权边"被误当作"负环" | 检查 d[i][i] < 0 的顶点;区分"存在负权边"与"存在总权为负的环"(2.4.4 节) |
排查这类问题的通用手段有两类证据:
- 中间状态:距离数组与已确定标记、优先队列中的条目数(惰性删除下应可观察到重复条目)、并查集的分量数、每条边的松弛次数。算法的缺陷大多表现为"不变式被破坏",这些量能把不变式的变化暴露出来;
- 不变式自检:
- 最短路满足三角不等式:对每条边 (u, v, w),应有
dist[v] ≤ dist[u] + w(非负权),违反即说明存在未完成的松弛; - 最短路径树中,每个顶点的
dist应等于其父节点dist加上两者之间边的权; - 生成树应满足边数 = V−1 且无环;总权可通过对边集求和独立复算;
- 并查集可验证"同一分量内任意两点的根相同"。
这类自检代价为线性(O(V+E)),可在测试与预发环境常态开启。
3.9 检查清单
3.9.1 算法选择依据表
| 判据 | 取值 | 推荐算法 |
|---|---|---|
| 边权特征 | 全部非负 | Dijkstra(堆或朴素,按图密度选) |
| 含负权、无负环 | Bellman-Ford 或 SPFA | |
| 含负环 | 先检测并报告无解 | |
| 图规模与密度 | 稀疏(E≈V) | Dijkstra/Prim 用堆;Kruskal |
| 稠密(E≈V²) | Dijkstra/Prim 用数组 O(V²);Floyd | |
| 求解范围 | 单源 | Dijkstra / Bellman-Ford / SPFA |
| 多源 | 逐源运行单源算法,或加虚拟源 | |
| 全源 | Floyd(V 小)或逐源 Dijkstra / Johnson(稀疏) | |
| 是否有启发信息 | 有可靠方向估计(地图、状态空间) | A* |
| 无可靠估计 | Dijkstra | |
| 是否需要生成树 | 连接全部顶点、总权最小 | Prim(稠密)或 Kruskal(稀疏/非连通) |
| 是否有向 | 有向图 | 最短路径可用,生成树需改用最小树形图 |
| 是否为 DAG | 是 | 按拓扑序线性求解,允许负权 |
3.9.2 实现自检项
- 距离数组的类型是否足够宽(
long);无穷大哨兵是否避免了两哨兵相加溢出。 - Dijkstra 是否确认了边权非负;是否用
done处理了惰性删除的过期条目;done是否在第一次取出时置位。 - 优先队列的比较键是否正确:Dijkstra 与 Prim 比较边/距离,A* 比较 f = g + h。
- Bellman-Ford 是否设置了提前退出;负环检测是否放在 n−1 轮之后;是否只从可达顶点松弛。
- SPFA 是否同时维护
in_queue与入队计数;入队阈值是否为 V;是否意识到最坏复杂度为 O(V·E)。 - Floyd 的 k 是否在最外层;哨兵值是否避免加法溢出;路径还原用的是
next[i][k]而不是next[k][j]。 - A* 的启发函数是否可采纳(从不高估);若要求关闭集安全,是否满足一致性;入堆键是否为 f。
- Prim 的堆键是否为"到树的单边权"(而非累计距离);朴素版本是否用
minEdge数组而非优先队列。 - Kruskal 的边是否按权升序排序;无向图每条边是否只存一次;并查集是否同时做路径压缩与按大小/秩合并。
- 图的存储是否与算法匹配:邻接表用于堆实现与 Prim,邻接矩阵用于稠密图与 Floyd。
- 是否处理了自环与重边;边数是否可能超过容量预估;V 与 E 的类型是否足够宽。
- 是否对不连通图做了处理(最小生成森林;最短路返回不可达标记)。
- 性能结论是否来自基准框架,是否记录了 V、E、密度、边权分布与实现版本。
四、总结
最短路径与最小生成树是带权图上两类最基本的优化问题,它们的全部差异可以归结为一句判断:优化的是"两点之间的路径代价",还是"连接全部顶点的总代价"。前者给出最短路径树,后者给出最小生成树;前者依赖源点,后者是全局的;两者在带权图上一般不可互相替代,把 MST 上的路径当作最短路径是反复出现的误解。
原理层面的主线:
- 前提条件决定算法可用性。边权是否非负、是否存在负环、图是否有向、是需要单源还是全源、是稀疏还是稠密,这五个判断在写下第一行代码之前就决定了算法族的选择。算法选错的代价远大于实现细节的失误。
- 松弛是全部最短路算法的共同动作。Dijkstra 用贪心决定松弛顺序(每次取最近顶点),Bellman-Ford 用轮次决定(反复扫描全部边),Floyd 用动态规划决定(按允许的中间点集合分层),A* 用启发调整顺序(按 f = g + h 排序)。它们都在做
dist[v] = min(dist[v], dist[u] + w),区别只在"以什么顺序松弛"以及"由此得到的复杂度与正确性边界"。 - Dijkstra 的正确性建立在非负边权之上。非负保证了"取出即确定"的不变式,从而允许贪心不再回头;负权一旦出现,绕行可能更省,不变式被破坏,算法失效。这一条界线把最短路算法分成非负权与支持负权两组。
- Bellman-Ford 用最朴素的遍历换取通用性。V−1 轮的界来自"简单路径至多 V−1 条边";第 V 轮的失效判定给出负环检测。SPFA 只是它的队列加速形式,平均快而最坏界为 O(V·E)。
- Floyd 把全源问题变成动态规划。状态"只允许前 k 个顶点作为中间点"给出三项递推,k 必须在最外层;空间可原地滚动到 O(V²);正对角线为负即存在负环。
- A 是 Dijkstra 加上方向信息*。可采纳的启发保证最优,一致的启发使关闭集安全;h ≡ 0 即退化为 Dijkstra,h 高估则失去最优性保证。启发函数的设计直接决定扩展顶点数量。
- 最小生成树的两条性质对应两种构造思路。割性质支持"从树向外逐步添加横跨割的最小边"(Prim),环性质支持"按权升序加边并跳过成环的边"(Kruskal)。两种算法都在每一步选择一条安全边,最终得到总权最小的生成树。
- 生成树不唯一,总权唯一。相等权值使同一张图可能存在多棵 MST;次小生成树用环性质(替换环上最大边)在最小生成树的基础上求得最小代价的替代方案。
- 两类问题常以子过程嵌入更大问题。拓扑排序后的 DAG 最短路 O(V+E)、Johnson 的重标号加逐源 Dijkstra、最小费用最大流中的最短路增广、关键路径分析中的 DAG 最长路,都说明算法族的边界是流动的,理解每个算法解决了什么子问题比记住它的名字更重要。
实现与工程层面需要落到位的几点:
- 数据结构的选择与图密度绑定。邻接表配堆适合稀疏图,邻接矩阵配线性扫描或 Floyd 适合稠密图;堆实现的 O((V+E) log V) 在稠密图上反而不如朴素 O(V²),"堆一定更快"是错误经验。
- 惰性删除是标准库优先队列的通用替代。不提供 decrease-key 时,插入更优条目并在取出时跳过过期项,是 Dijkstra、Prim、A* 的共同写法,代价是堆中条目数从 O(V) 升到 O(E)。
- 负权的处理顺序是先检测负环,再求最短路径。可达负环意味着问题无解;Bellman-Ford 检测从源可达的负环,Floyd 检测全图负环。
- 启发函数的性质决定 A 的结论*。可采纳保证最优,一致保证关闭集安全;提速应通过带权 A* 显式进行,而不是使用高估的启发。
- 并查集的两项优化共同作用。按秩/按大小合并使树高有界,路径压缩使查找近常数,二者合用得到摊还 O(α(n))。这是 Kruskal 复杂度结论的一部分,也是"摊还结论依赖结构不变量"的又一个例子。
- 选型依据是前提条件而不是算法排名。边权特征、图规模、求解范围、是否有启发、是否需要生成树,构成一张足以覆盖大多数场景的决策表(3.9.1 节)。
从一点到另一点的最小代价,与把所有点连成一体的最小总代价,构成了带权图上最基础的两类优化。掌握它们的共同动作(松弛)与各自的前提边界(非负权、无环、连通、有向),以及实现层面的结构取舍(堆与数组、邻接表与矩阵、并查集与懒惰删除),就可以在具体的路由、导航、布线、调度问题中做出有依据的选择。