3. 最短路径问题定义与变体

最短路径问题是图论与网络优化中最基础、应用最广的一类问题。它的形式化定义是：给定一个带权有向图或无向图 G = (V, E)，每条边 (u, v) 具有权重 w(u, v)，再给定起点 s 与终点 t，求一条从 s 到 t 的路径，使路径上所有边权之和最小。这个"和"称为路径长度或路径代价。理解最短路径，关键不在于记住某个算法，而在于先分清"问的是哪一类问题"，再据此选择算法。

需要先明确一个约定：本文中边权可正可负，路径长度定义为边权之和；若图中存在负权边，则"最短"可能不存在（负环情形），这一点后文专门讨论。所有图示与文字均采用同一约定。

四种基本变体及其本质差异

按"起点与终点的组合方式"，最短路径问题可分为四类，它们的计算规模与适用算法差异很大：

• 单源最短路径（SSSP）：固定一个源点 s，求 s 到所有其他顶点的最短距离。输出是一棵以 s 为根的最短路径树。典型算法：Dijkstra（非负权）、Bellman-Ford（可含负权）、SPFA（Bellman-Ford 的队列优化）。
• 单对最短路径：只求指定 s 到指定 t 的一条最短路径。看似比 SSSP 简单，但在一般图上并没有比 SSSP 更快的已知算法（最坏情况仍需解 SSSP），因此实践中通常直接跑一次 SSSP 再取 t 的结果。
• 全源最短路径（APSP）：求任意两点间的最短距离，输出是一个 n×n 的距离矩阵。典型算法：Floyd-Warshall（O(n³)，可含负权、可检测负环）、Johnson 算法（稀疏图更优，先重赋权再用 Dijkstra）。
• 多源最短路径：给定多个源点，求每个顶点到最近源点的距离。常用技巧是引入超级源点 S，向所有源点连一条权为 0 的边，转化为单源问题。

下图概括了这几种变体之间的关系、输入输出形态以及算法选择的分支逻辑：

负权边与负环：为什么它们改变了游戏规则

Dijkstra 的正确性依赖一个贪心前提：一旦某顶点被取出，它的距离就是最终最短距离。这个前提只在所有边权非负时成立。若存在负权边，一条"绕远"的路径可能因为负权边而变得更短，Dijkstra 会过早锁定错误结果。因此含负权时必须改用 Bellman-Ford 类算法。

Bellman-Ford 的核心是"松弛"操作：对每条边 (u, v)，若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]。它把所有边松弛 V-1 轮，因为任意最短路径最多含 V-1 条边。第 V 轮若仍能松弛成功，说明存在负环——即一个边权之和为负的环。沿负环可以无限绕行使路径长度趋于负无穷，此时"最短路径"在数学上不存在。

一个可手算的教学示例

设图有 4 个顶点 A、B、C、D，边为：A→B 权 4，A→C 权 5，B→C 权 −3，C→D 权 2，B→D 权 6。以 A 为源点，初始化 dist = [0, ∞, ∞, ∞]。

第 1 轮松弛：A→B 得 dist[B]=4；A→C 得 dist[C]=5；B→C 得 4+(−3)=1 < 5，更新 dist[C]=1；C→D 得 1+2=3；B→D 得 4+6=10，不更新。第 2 轮再检查，无更优更新，收敛。最终 dist = [0, 4, 1, 3]。注意 C 的最短距离 1 正是借助负权边 B→C 得到的，若用 Dijkstra 会先锁定 dist[C]=5 而得到错误答案。此例为教学构造，用于说明负权边的影响，非实测数据。

算法选择的实践依据

实际选型时，可按以下顺序判断：第一，看边权是否可能为负——有负权则排除 Dijkstra，选 Bellman-Ford/SPFA，并做负环检测；第二，看输出需求——只需单源就做一次 SSSP，需要任意两点则考虑 APSP；第三，看图规模与稀疏度——稠密小图用 Floyd-Warshall 简洁可靠，稀疏大图用 Johnson 或对每个源跑 Dijkstra；第四，看是否有动态更新、多源等特殊需求，再叠加超级源点、重赋权等技巧。把"问题变体"和"边权符号"这两个维度先定下来，算法选择基本就唯一了。