一、起源:两类带权图的优化需求

图由顶点集合与连接顶点的边集合构成,边可以携带代价(长度、时延、费用、权重)。一旦边上有了数值,"选择哪些边"就从一个结构问题变成了优化问题。本文讨论两类最基本的优化问题,它们的区别在于优化的目标范围:一类只关心两个顶点之间的代价,另一类关心连接全部顶点的总代价。

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·单源
多对多 多组指定的点对 按点对分别求解或用全源结果查表 取决于点对数量

几点说明:

  1. "多源"不等于"全源"。多源指有多个起点需要各自求出到全图(或到某集合)的距离,其解仍是若干组单源结果,可以用单源算法逐个源点运行;全源指需要任意两点这一完整矩阵,若图稠密,V 次单源算法的代价会超过 Floyd。
  2. 虚拟源技巧。若若干源点只需到达同一集合(例如"最近的配送中心"),可以引入一个到所有源点代价为 0 的虚拟源,一次单源求解即得到"任意点到最近源点"的距离,无需逐个源点运行。
  3. 单源最短路的结果包含一棵树。以源点为根,把每个顶点的最短路径上的前驱边连起来,得到的是一棵以源为根的有向树,称为最短路径树(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 无向与有向

  • 无向图的边可以双向通行,等价于两条方向相反、权相同的边。
  • 有向图的边有方向,只沿边的指向通行。路由、依赖关系、状态转移都是有向的。

两处容易出错的地方:

  1. 无向图的负权边必然产生负环。一条权为负的无向边,来回走一次(u→v→u)即构成总权为负的环,因此无向图中出现负权边时,最短路径问题直接无解。这一结论把负权场景限制在有向图上。
  2. 最小生成树算法主要针对无向图。生成树要求"连通所有顶点",有向图中的对应概念是"有向生成树"(从根出发可达所有顶点),其算法不同(如最小树形图/朱刘算法)。把 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)

几点说明:

  1. 二项的关键差别在减键(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²) 量级。各类优先队列的操作代价对照见 堆与优先队列 中图算法中的优先队列一节。
  2. 标准库通常不提供减键接口。实现上改用惰性删除:不修改堆中的旧记录,而是插入一条更优的新记录;取出时校验该顶点是否已确定,已确定则丢弃并继续取下一个(3.1 节)。这一做法的复杂度与二叉堆减键同阶(均摊意义下),代价是堆中元素数可达 O(E) 而非 O(V)。
  3. 朴素实现的价值。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) 排序 + 并查集 稀疏图、非连通图、边较易枚举

选择依据:

  1. 稠密图(E 接近 V²)选 Prim 的数组实现。O(V²) 优于 O(E log V) = O(V² log V);且稠密图下数组的连续访问比堆的跳跃访问更适合缓存。
  2. 稀疏图(E 与 V 同阶)选 Kruskal。O(E log E) 与 O(E log V) 量级相近,而 Kruskal 只需一次排序加并查集,实现更简单,且不要求图连通。
  3. 边以列表形式给出时选 Kruskal,它不依赖邻接结构;需要从某个起点生长、或边难以一次性枚举时选 Prim。
  4. 理论上界不等于实测:小规模与稠密图上两者差异由常数项主导,结论应来自实测。

2.6.5 生成树不唯一与次小生成树

生成树不唯一。 当图中存在权值相等的边时,同一张图可能有多棵总权相同的最小生成树。例如一个正方形四个顶点、四条边权都为 1:任选其中三条边即得一棵 MST,共四棵。因此"求出最小生成树"通常指求出任一棵(总权确定),而不是求出唯一的边集。若需报告所有 MST 或判断某条边是否属于某棵 MST,需要额外的枚举或计数方法。

次小生成树。 在少数场景下,仅有一棵生成树不足以满足冗余性要求(例如需要一条备用链路)。次小生成树指总权严格大于或等于最小生成树、且在所有生成树中总权次小的那棵。常见求法是利用环性质:

  1. 先求一棵最小生成树 T;
  2. 对每条不在 T 中的边 (u, v, w),它加入 T 后形成一个唯一环,设环上除它之外的最大边权为 maxW;
  3. 用该边替换环上最大边,得到一棵总权为 sum(T) − maxW + w 的新生成树;
  4. 枚举所有非树边,取上述值最小者即次小生成树。

这一方法用到环性质(替换环上最大边),是"环性质用于判定某条边可否被替换"的直接应用。

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 与拓扑排序、网络流的区别

拓扑排序处理的是有向无环图的顶点排序,使每条边都从较前的顶点指向较后的顶点。它与最短路径的关系有两点:

  1. DAG 上的最短路径可以按拓扑序线性求解,代价 O(V+E),比 Dijkstra 更快,且允许负权(无环即无负环);
  2. 拓扑排序是"按顺序"推进,最短路算法是"按代价"推进:前者只依赖边的方向,后者依赖边的权值与松弛。两者的推进依据不同,不能混用。

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) 视实现 不适用

读数要点:

  1. Dijkstra 的堆实现只在稀疏图上优于朴素实现。稠密图(E 接近 V²)时 (V+E) log V 与 V² log V 反而不如 V²,此时应回退到朴素版本;
  2. Floyd 的复杂度与 E 无关,稠密图上是自然选择,稀疏图上应改用逐源 Dijkstra 或 Johnson;
  3. Kruskal 的 O(E log E) 在稠密图上退化为 O(V² log V),此时 Prim 的 O(V²) 更优;
  4. 复杂度只是筛选器,相同量级下实际快慢由常数、缓存、实现细节决定。

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 节)

排查这类问题的通用手段有两类证据:

  1. 中间状态:距离数组与已确定标记、优先队列中的条目数(惰性删除下应可观察到重复条目)、并查集的分量数、每条边的松弛次数。算法的缺陷大多表现为"不变式被破坏",这些量能把不变式的变化暴露出来;
  2. 不变式自检:
  • 最短路满足三角不等式:对每条边 (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 节)。

从一点到另一点的最小代价,与把所有点连成一体的最小总代价,构成了带权图上最基础的两类优化。掌握它们的共同动作(松弛)与各自的前提边界(非负权、无环、连通、有向),以及实现层面的结构取舍(堆与数组、邻接表与矩阵、并查集与懒惰删除),就可以在具体的路由、导航、布线、调度问题中做出有依据的选择。