【数据结构与算法体系】之图算法（三）-单源最短路径

问题定义

单源最短路径（Single-Source Shortest Path, SSSP）问题：给定带权有向图 $G = (V, E)$ 和源点 $s \in V$，找出从 $s$ 到所有其他顶点 $v \in V$ 的最短路径。

最短路径的权值定义为路径上所有边的权值之和：
$$\delta(s, v) = \min\left{\sum_{(u_i, u_{i+1}) \in P} w(u_i, u_{i+1}) \ \middle|\ P \text{ 是从 } s \text{ 到 } v \text{ 的路径}\right}$$

若不存在从 $s$ 到 $v$ 的路径，则 $\delta(s, v) = \infty$。

前置概念：松弛操作（Relaxation）

几乎所有最短路径算法的核心都是松弛。对于边 $(u, v)$，松弛操作检查是否可以通过 $u$ 改善到达 $v$ 的最短路径估计值 $d[v]$：

Relax(u, v, w):
    if d[v] > d[u] + w(u, v):
        d[v] = d[u] + w(u, v)
        π[v] = u          // 记录前驱节点，用于重建路径

其中 $d[v]$ 是从源点 $s$ 到 $v$ 的当前最短路径估计（上界），$π[v]$ 是 $v$ 在最短路径树中的前驱节点。初始时 $d[s] = 0$，其余 $d[v] = \infty$。

松弛操作的核心性质：

• 上界性质：对于所有 $v \in V$，始终有 $d[v] \geq \delta(s, v)$
• 收敛性质：若 $s \leadsto u \to v$ 是某条最短路径且松弛 $(u, v)$ 前 $d[u] = \delta(s, u)$，则松弛后 $d[v] = \delta(s, v)$
• 路径松弛性质：按最短路径上的边顺序依次松弛，最终 $d[v] = \delta(s, v)$

---

一、Dijkstra 算法

1.1 核心思想

Dijkstra 采用贪心策略：每次从尚未确定最短距离的顶点中选择 $d[v]$ 最小的顶点，将其标记为”已确定”，然后松弛其所有出边。

该贪心策略正确的前提条件：所有边的权值非负（$w(u, v) \geq 0$）。

正确性直觉：在非负权值下，已确定的最短距离不可能再被任何后续顶点改善——因为后续顶点距离更大，加上非负边权只会更大。

1.2 算法伪代码

Dijkstra(G, w, s):
    1.  Initialize-Single-Source(G, s)
    2.  S = ∅                           // 已确定最短距离的顶点集合
    3.  Q = V                            // 最小优先队列，按 d[v] 排序
    4.  while Q ≠ ∅:
    5.      u = Extract-Min(Q)           // 取出 d 值最小的顶点
    6.      S = S ∪ {u}
    7.      for each vertex v ∈ Adj[u]:
    8.          Relax(u, v, w)           // 若 d[v] > d[u] + w(u,v)，更新 d[v]
    9.          // 若 d[v] 减小，Q 中执行 Decrease-Key

1.3 时间复杂度分析

Dijkstra 的性能瓶颈在于优先队列操作。每条边最多触发一次松弛（即一次 Decrease-Key），共 $|V|$ 次 Extract-Min。

优先队列实现	Extract-Min	Decrease-Key	总复杂度
无序数组	$O(V)$	$O(1)$	$O(V^2)$
二叉堆（Binary Heap）	$O(\log V)$	$O(\log V)$	$O((V+E)\log V)$
斐波那契堆（Fibonacci Heap）	$O(\log V)$ 均摊	$O(1)$ 均摊	$O(V\log V + E)$

• 稠密图（$E \approx V^2$）：用数组实现，$O(V^2)$ 实际上优于二叉堆的 $O(V^2\log V)$
• 稀疏图（$E \approx V$）：用二叉堆实现，$O(V\log V)$
• 理论上最优：斐波那契堆，但常数因子大，实际中不常用

1.4 完整实现（二叉堆版本）

public class Dijkstra {
    public static int[] shortestPath(List<List<Edge>> graph, int s) {
        int n = graph.size();
        int[] dist = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[s] = 0;

        // 最小堆: (顶点, 距离)
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.dist));
        pq.offer(new Node(s, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;

            // 惰性删除：跳过已处理的旧条目
            if (node.dist > dist[u]) continue;

            for (Edge e : graph.get(u)) {
                int v = e.to;
                int newDist = dist[u] + e.weight;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.offer(new Node(v, newDist));
                }
            }
        }
        return dist;
    }

    // 重建最短路径
    public static List<Integer> reconstructPath(int[] prev, int target) {
        List<Integer> path = new ArrayList<>();
        for (int v = target; v != -1; v = prev[v]) {
            path.add(v);
        }
        Collections.reverse(path);
        return path;
    }
}

实现要点：

• 使用惰性删除（Lazy Deletion）：不实现 Decrease-Key，而是将新的更小距离直接入堆。当从堆中取出顶点时，若 node.dist > dist[u] 说明该条目已经过期，直接跳过。这在实际中通常比手动 Decrease-Key 更快。
• 空间复杂度：优先队列中可能有 $O(E)$ 个条目（每条边一次松弛产生一个新条目）。

1.5 Dijkstra 的局限性

不能处理负权边。考虑以下反例：

s ── 2 ──▶ u
│          │
│ -3       │ 1
▼          ▼
v ◀── 1 ──┘

Dijkstra 从 $s$ 出发，先确定 $d[v]=-3$（走 $s \to v$），然后确定 $d[u]=2$（走 $s \to u$）。但实际上存在更短的路径 $s \to u \to v$ 使得 $d[v] = 2 + 1 = 3$，这比 $-3$ 更大，没问题。

但若有负权边 $s \to u(w=2), s \to v(w=4), u \to v(w=-3)$：

• Dijkstra 先确定 $d[v]=4$（直接路径），然后发现 $d[u]=2$
• 通过 $u$ 松弛 $v$：$d[v] = 2 + (-3) = -1$，但这已经晚了——$v$ 已被错误地 “确定” 为距离 4

核心原因：Dijkstra 的贪心假设了从小到大的距离顺序，负权边打破了这个顺序。

---

二、Bellman-Ford 算法

2.1 核心思想

Bellman-Ford 基于动态规划思想：对图中所有边重复松弛 $|V|-1$ 轮。第 $k$ 轮松弛后，最多经过 $k$ 条边的最短路径被正确计算。

为什么是 $|V|-1$ 轮？ 一条不包含环的最短路径最多包含 $|V|-1$ 条边。第 $k$ 轮松弛保证找出所有包含不超过 $k$ 条边的最短路径。

2.2 算法伪代码

Bellman-Ford(G, w, s):
    1.  Initialize-Single-Source(G, s)
    2.  for i = 1 to |V| - 1:
    3.      for each edge (u, v) ∈ E:
    4.          Relax(u, v, w)
    5.  // 检测负权环
    6.  for each edge (u, v) ∈ E:
    7.      if d[v] > d[u] + w(u, v):
    8.          return FALSE           // 存在负权环
    9.  return TRUE

2.3 实现

public class BellmanFord {
    public static int[] shortestPath(int n, List<Edge> edges, int s) {
        int[] dist = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[s] = 0;

        // 松弛 |V|-1 轮
        for (int i = 1; i < n; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                if (dist[e.from] != Integer.MAX_VALUE 
                    && dist[e.to] > dist[e.from] + e.weight) {
                    dist[e.to] = dist[e.from] + e.weight;
                    prev[e.to] = e.from;
                    updated = true;
                }
            }
            if (!updated) break;  // 早期退出：本轮无更新则已收敛
        }

        // 检测负权环
        for (Edge e : edges) {
            if (dist[e.from] != Integer.MAX_VALUE 
                && dist[e.to] > dist[e.from] + e.weight) {
                throw new RuntimeException("图中存在负权环");
            }
        }

        return dist;
    }
}

优化——早期退出：若某一轮中没有发生任何松弛，则算法已收敛，可以提前终止。在随机图上，这通常能在远少于 $|V|-1$ 轮内完成。

2.4 时间复杂度

• 基本版：$O(VE)$，对稠密图可达 $O(V^3)$
• 加上早期退出后，平均情况远优于最坏情况
• 稀疏图上通常可行，稠密图考虑 Dijkstra

2.5 负权环检测

Bellman-Ford 的核心优势是能检测负权环。在第 $|V|$ 轮（或单独一轮）中如果还能松弛任何边，说明存在负权环——因为不包含环的最短路径最多 $|V|-1$ 条边，能继续改善意味着路径中含有环，且环的权值和为负。

负权环检测的实际意义：

• 套利检测：货币兑换图中，负权环 = 无风险套利机会
• 差分约束系统：若 Bellman-Ford 检测到负环，说明约束不可满足
• 网络路由：BGP 等协议需要检测路由环路

---

三、SPFA 算法（Shortest Path Faster Algorithm）

3.1 核心思想

SPFA 是 Bellman-Ford 的队列优化版本。Bellman-Ford 每轮盲目松弛所有边，但只有上一轮距离被更新的顶点，其出边才需要在本轮松弛。

SPFA 使用一个队列维护”距离刚被更新、需要用于松弛的顶点”。

3.2 算法伪代码

SPFA(G, w, s):
    1.  Initialize-Single-Source(G, s)
    2.  Q = Queue()
    3.  Q.enqueue(s)
    4.  inQueue[s] = TRUE
    5.  while Q ≠ ∅:
    6.      u = Q.dequeue()
    7.      inQueue[u] = FALSE
    8.      for each edge (u, v) ∈ Adj[u]:
    9.          if d[v] > d[u] + w(u, v):
   10.              d[v] = d[u] + w(u, v)
   11.              if not inQueue[v]:
   12.                  Q.enqueue(v)
   13.                  inQueue[v] = TRUE
   14.                  enqueueCount[v]++
   15.                  // 若某顶点入队超过 |V| 次，存在负权环
   16.                  if enqueueCount[v] > |V|:
   17.                      return NEGATIVE_CYCLE

3.3 实现

public class SPFA {
    public static int[] shortestPath(List<List<Edge>> graph, int s) {
        int n = graph.size();
        int[] dist = new int[n];
        int[] enqCount = new int[n];
        boolean[] inQueue = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        inQueue[s] = true;
        enqCount[s] = 1;

        while (!q.isEmpty()) {
            int u = q.poll();
            inQueue[u] = false;

            for (Edge e : graph.get(u)) {
                int v = e.to;
                if (dist[v] > dist[u] + e.weight) {
                    dist[v] = dist[u] + e.weight;
                    if (!inQueue[v]) {
                        q.offer(v);
                        inQueue[v] = true;
                        enqCount[v]++;
                        if (enqCount[v] > n) {
                            throw new RuntimeException("负权环");
                        }
                    }
                }
            }
        }
        return dist;
    }
}

3.4 SPFA 的争议

SPFA 在国际信息学奥赛中广泛使用，但学术界对其颇有微词：

• 最坏情况：$O(VE)$，与 Bellman-Ford 相同。特定构造的图可以使 SPFA 退化到最坏情况（网格图 + 特定边权）
• 随机图：表现通常接近 $O(E)$
• 实际建议：正权图用 Dijkstra，负权图用 Bellman-Ford。SPFA 在某些场景（如费用流）中有用，但不建议作为通用最短路径算法
• 2018 年，SPFA 被发现在大量竞赛题目中可以被卡到指数级，引发了广泛讨论

---

四、三种算法对比

维度	Dijkstra	Bellman-Ford	SPFA
适用边权	非负	任意（可检测负环）	任意（可检测负环）
贪心 vs DP	贪心	动态规划	队列优化的 DP
时间复杂度	$O((V+E)\log V)$	$O(VE)$	平均 $O(E)$，最坏 $O(VE)$
空间复杂度	$O(V)$	$O(V)$	$O(V)$
适用图	正权	任意	任意（但可能退化）
实现难度	中等	简单	简单
稳定性	稳定	稳定（可预测）	不稳定（可能被卡）
并行化	困难（依赖全局最小值）	容易（每轮独立松弛）	困难（队列依赖）

选择建议

• 正权图 → Dijkstra：这是绝大多数实际场景。社交网络、地图导航、网络路由的链路代价都非负
• 含负权边 → Bellman-Ford：金融计算、差分约束系统。当需要严格的最坏情况保证时选择
• 算法竞赛 → 视情况：正权图绝对用 Dijkstra（SPFA 被刻意卡掉的概率很大）

---

五、Dijkstra 的正确性证明

定理：在非负权值图中，Dijkstra 算法正确计算所有顶点的最短路径距离。

证明（归纳法）：

设 $S$ 为已从优先队列中取出（距离已确定）的顶点集合。

归纳假设：对于所有 $u \in S$，$d[u] = \delta(s, u)$。

基础：$|S| = 1$ 时，$S = {s}$，$d[s] = 0 = \delta(s, s)$。

归纳步骤：设 $u$ 是下一次 Extract-Min 从 $Q$ 中取出的顶点（$u \notin S$）。我们要证 $d[u] = \delta(s, u)$。

假设存在一条比 $d[u]$ 更短的从 $s$ 到 $u$ 的路径 $P$。路径 $P$ 从 $S$ 中的顶点出发，最终到达 $u$（$u \notin S$）。设 $(x, y)$ 是 $P$ 中第一条离开 $S$ 的边（$x \in S$, $y \notin S$）。

路径 $P$ 可分解为 $s \leadsto x \to y \leadsto u$。$x \in S$ 已确定最短距离，因此：
$$d[y] \leq d[x] + w(x, y) \quad \text{（松弛保证）}$$
$$= \delta(s, x) + w(x, y) \quad \text{（归纳假设）}$$
$$\leq \delta(s, x) + w(x, y) + \delta(y, u) \quad \text{（非负权值保证 } \delta(y, u) \geq 0 \text{）}$$
$$= \delta(s, u) \quad \text{（最短路径的最优子结构）}$$

因此 $d[y] \leq \delta(s, u) < d[u]$（反证假设 $P$ 比 $d[u]$ 短）。但这与 $u$ 是 Extract-Min 选出的最小元素矛盾（$d[y] < d[u]$，$y$ 应在 $u$ 之前被取出）。

因此不存在更短的路径，即 $d[u] = \delta(s, u)$。

注意：此证明关键依赖于非负权值（$\delta(y, u) \geq 0$）。若存在负权边，该不等式不成立，贪心策略失效。

---

六、差分约束系统与 Bellman-Ford

6.1 问题转化

差分约束系统是一组形如 $x_j - x_i \leq c_k$ 的不等式。这类问题可以转化为图论中的最短路径问题：

将每个变量 $x_i$ 映射为图中的一个顶点。对每个约束 $x_j - x_i \leq c_k$，添加一条从 $i$ 到 $j$ 的边，权值为 $c_k$。

定理：差分约束系统有解当且仅当对应的约束图中不存在负权环。且一组可行解为 $x_i = \delta(v_0, i)$，其中 $v_0$ 是新增的超级源点（通过权值为 0 的边连接所有顶点）。

6.2 应用场景

• 任务调度中的时间约束
• VLSI 芯片设计中的布局约束
• 编译器中指令调度的依赖约束

---

七、常见变体与扩展

7.1 所有结点对最短路径

当需要所有顶点对之间的最短距离时，可以：

• 对每个顶点运行一次 Dijkstra：$O(V \cdot (V+E)\log V)$，适用于稀疏正权图
• Floyd-Warshall：$O(V^3)$，可处理负权边，基于 DP
• Johnson 算法：$O(V^2\log V + VE)$，先用 Bellman-Ford 做一次重赋权消除负权，再跑 $V$ 次 Dijkstra

7.2 A* 搜索

Dijkstra 的启发式扩展。使用估价函数 $f(v) = g(v) + h(v)$，其中 $g(v)$ 是当前已知距离，$h(v)$ 是到目标的启发式估计。若 $h(v)$ 是可采纳的（不高估），A* 保证最优。广泛用于游戏 AI 和地图导航。

7.3 双向 Dijkstra

从源点和目标同时运行 Dijkstra，当两个搜索前沿相遇时停止。将搜索空间减少约一半（$O(\sqrt{V})$ 级别），广泛用于实际的地图导航系统。

---

面试常考问题

Q1：为什么 Dijkstra 不能处理负权边？给出反例并解释根本原因。

Dijkstra 的贪心策略基于”一旦顶点从优先队列中取出，其距离就不可能再被改善”。这个前提依赖非负权值。反例：$s \to u(w=2), s \to v(w=4), u \to v(w=-3)$。Dijkstra 先以距离 2 取出 $u$，再以距离 4 取出 $v$ 并标记确定。但随后松弛 $(u, v)$ 发现到 $v$ 更短的路径 $2+(-3)=-1$，而此时 $v$ 已被错误确定。根本原因：负权边意味着”绕远路可能更短”，违反了贪心选择的前提。

Q2：Bellman-Ford 为什么需要恰好 $|V|-1$ 轮？

不含环的简单路径最多包含 $|V|-1$ 条边。第 $k$ 轮松弛保证所有不超过 $k$ 条边的最短路径被正确计算。如果存在包含 $|V|$ 条边的”更短”路径，该路径必然含有环，且环权和必须为负（否则去掉环不会更长）。第 $|V|$ 轮还能松弛意味着存在负权环。

Q3：什么场景下应该选 SPFA 而非 Dijkstra 或 Bellman-Ford？

SPFA 的实际意义非常有限。正权图一定用 Dijkstra（稳定性保证，且现代 CPU 上堆操作很快）。需要检测负环时 Bellman-Ford 的可预测性更好。SPFA 仅在特定场景——如图的边权动态变化需要增量更新（费用流算法的内部循环）、或大量松弛无效时 SPFA 的队列优化优势明显——才有使用价值。面试中明确说”优先 Dijkstra，必要负权选 Bellman-Ford”即可。

Q4：如何从 dist[] 和 prev[] 数组重建最短路径？

List<Integer> path = new ArrayList<>();
for (int v = target; v != -1; v = prev[v]) {
    path.add(v);
}
Collections.reverse(path);

如果 prev[target] == -1 且 target != s，说明不存在从源点到目标的路径。路径的边数 = path.size() - 1。

Q5：Dijkstra 用斐波那契堆理论上更优，为什么实际中几乎不用？

斐波那契堆的 Decrease-Key 是 $O(1)$ 均摊，但常数因子极大（维护级联剪切、标记位等）。在实际图规模下（$V$ 在 $10^3 \sim 10^6$ 级），二叉堆的 $O(\log V)$ 足够快，且二叉堆的内存局部性好、实现简单。此外，很多 Dijkstra 实现使用惰性删除（不实现 Decrease-Key），此时斐波那契堆的优势完全丧失。工业界（如 OSRM、GraphHopper 等路由引擎）几乎一致使用二叉堆或其变种。