图论算法全解析（二）：最短路径三部曲

2026-05-18

引言 (Introduction)

最短路径是图论中最具工程价值的算法族。从导航软件的路径规划到网络路由协议（OSPF 基于 Dijkstra，RIP 基于 Bellman-Ford），最短路径算法支撑着现代互联网的基础设施。

本文是本系列第二篇。在掌握了 BFS（无权图最短路径）的基础上，我们将攻克带权图最短路径的三种经典算法：Dijkstra、Bellman-Ford 和 Floyd-Warshall。三种算法的适用场景各不相同——选择正确的算法本身就是一项核心能力。

1. Dijkstra 算法

1.1 算法思想

Dijkstra 是一种贪心算法：每次从「未确定最短距离」的节点中选出距离起点最近的节点，将其标记为「已确定」，并用它来松弛其邻居。

前提：所有边权非负。一旦存在负权边，贪心假设失效（已确定的节点可能被负权边绕过而更新）。

在贪心系列中我们已提过 Dijkstra 的贪心本质，这里给出完整的优先队列实现。

1.2 完整代码

import heapq
from typing import Dict, List, Tuple

def dijkstra(graph: Dict[int, List[Tuple[int, int]]],
             start: int) -> Dict[int, int]:
    """
    graph: 邻接表 {u: [(v, weight), ...]}
    返回: {节点: 最短距离}
    """
    dist: Dict[int, int] = {start: 0}
    heap: List[Tuple[int, int]] = [(0, start)]  # (距离, 节点)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):    # 惰性删除：跳过旧条目
            continue

        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return dist

复杂度：时间 $O((V + E) \log V)$（堆操作），空间 $O(V)$。

惰性删除：同一个节点可能以不同的距离多次入堆（因为找到了更短的路径）。if d > dist[u] 检查跳过那些旧的、距离更大的堆条目。这是 Dijkstra 优先队列实现的标准技巧。

1.3 为什么 BFS 不能处理带权图？

BFS 的层序性质依赖于所有边的代价相等（均为 1）。当边权不同时，先入队的节点不一定比后入队的节点距离更短。优先队列替代普通队列，按距离而非层数排序——这是 Dijkstra 相对于 BFS 的核心升级。

2. Bellman-Ford 算法

2.1 算法思想

Bellman-Ford 是一种动态规划算法：对所有边进行 $V-1$ 轮松弛操作。第 $k$ 轮结束时，dist[v] 表示「经过最多 $k$ 条边到达 $v$ 的最短距离」。

DP 状态定义：$dp[k][v]$ = 最多经过 $k$ 条边到达 $v$ 的最短距离。

$$dp[k][v] = \min(dp[k-1][v],\ \min_{(u,v) \in E}(dp[k-1][u] + w(u, v)))$$

2.2 完整代码

from typing import List, Dict

def bellman_ford(n: int, edges: List[List[int]], start: int) -> List[int]:
    """
    n: 节点数（节点编号 0..n-1）
    edges: 边列表 [[u, v, w], ...]
    start: 起点
    返回: 到所有节点的最短距离，若存在负环则返回空列表
    """
    INF = float('inf')
    dist: List[float] = [INF] * n
    dist[start] = 0

    # 进行 n-1 轮松弛
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:               # 提前终止优化
            break

    # 第 n 轮检测负环
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return []                 # 存在负环

    return dist

复杂度：时间 $O(VE)$，空间 $O(V)$。

提前终止优化：如果某一轮没有任何 dist 值被更新，说明已收敛，可提前退出。

2.3 Bellman-Ford 的独特优势

特性	Dijkstra	Bellman-Ford
负权边	不支持	支持
负环检测	不支持	支持（第 $n$ 轮还更新即存在）
时间复杂度	$O((V+E)\log V)$	$O(VE)$
适用图	非负权图	任意图

使用场景：当图可能存在负权边，或需要检测负环时，Bellman-Ford 是唯一选择。

3. Floyd-Warshall 算法

3.1 算法思想

Floyd-Warshall 是区间 DP 在全源最短路径上的应用。状态定义：

$dp[k][i][j]$ = 使用节点集合 $\{0, 1, \ldots, k-1\}$ 作为中间节点时，$i$ 到 $j$ 的最短距离。

转移方程：

$$dp[k][i][j] = \min(dp[k-1][i][j],\ dp[k-1][i][k] + dp[k-1][k][j])$$

即要么不经过 $k$，要么经过 $k$（$i \to k \to j$）。空间优化可将 $k$ 维度压缩掉（原地更新）。

3.2 完整代码

from typing import List

def floyd_warshall(n: int, edges: List[List[int]]) -> List[List[int]]:
    """
    n: 节点数
    edges: 边列表 [[u, v, w], ...]
    返回: n×n 的最短距离矩阵
    """
    INF = float('inf')
    dist: List[List[float]] = [[INF] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # 处理平行边

    # 三重循环：k 必须在最外层
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

复杂度：时间 $O(V^3)$，空间 $O(V^2)$。

为什么 $k$ 循环必须在最外层？ 因为 $dp[k][i][j]$ 依赖 $dp[k-1][i][k]$ 和 $dp[k-1][k][j]$——第 $k$ 层的更新必须基于第 $k-1$ 层。若 $k$ 放在内层，会导致使用当前层（而非上一层）的中转点，破坏了 DP 的语义。在空间优化后（三维降二维），$k$ 为外层恰好保证了对每个 $k$，$i$ 和 $j$ 用的是上一轮 $k$ 的中间结果。

4. LeetCode 743：网络延迟时间

题目：$n$ 个节点的网络，从节点 $k$ 发送信号，求所有节点收到信号的最短时间（即 $k$ 到所有节点的最短距离的最大值）。

这是 Dijkstra 的直接应用。

import heapq
from typing import List, Dict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # 建图
        graph: Dict[int, List[tuple]] = {i: [] for i in range(1, n + 1)}
        for u, v, w in times:
            graph[u].append((v, w))

        # Dijkstra
        dist: Dict[int, int] = {}
        heap = [(0, k)]

        while heap:
            d, u = heapq.heappop(heap)
            if u in dist:
                continue
            dist[u] = d
            for v, w in graph[u]:
                if v not in dist:
                    heapq.heappush(heap, (d + w, v))

        return max(dist.values()) if len(dist) == n else -1

复杂度：时间 $O((n + |times|) \log n)$，空间 $O(n)$。

5. LeetCode 787：K 站内最便宜航班

题目：从 src 到 dst 最多经过 $k$ 次中转（即至多 $k+1$ 条边）的最便宜票价。

这是 Bellman-Ford 的自然应用——限制「最多 $k+1$ 条边」恰好对应 Bellman-Ford 的前 $k+1$ 轮松弛。

from typing import List

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]],
                          src: int, dst: int, k: int) -> int:
        INF = float('inf')
        dist: List[float] = [INF] * n
        dist[src] = 0

        # 最多 k+1 条边 = 进行 k+1 轮松弛
        for _ in range(k + 1):
            # 关键：用上一轮的 dist 副本，避免同一轮内串联松弛
            prev = dist[:]
            for u, v, w in flights:
                if prev[u] != INF and prev[u] + w < dist[v]:
                    dist[v] = prev[u] + w

        return int(dist[dst]) if dist[dst] != INF else -1

关键技巧：prev = dist[:] 确保每轮松弛使用上一轮的结果，而非本轮已被更新的值。这保证了「最多 $k+1$ 条边」的语义不被破坏。如果没有这个副本，一次松弛可能串联经过多条边，导致突破了中转次数限制。

6. LeetCode 1334：阈值距离内邻居最少的城市

题目：给定 $n$ 个城市的带权无向图，对每个城市统计「与其距离不超过 distanceThreshold 的城市数」，找出这个数量最少的城市。

这是 Floyd-Warshall 的直接应用——先求全源最短距离，再逐城市统计。

from typing import List

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]],
                    distanceThreshold: int) -> int:
        INF = float('inf')
        dist: List[List[float]] = [[INF] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for u, v, w in edges:
            dist[u][v] = dist[v][u] = w

        # Floyd-Warshall
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        # 统计每个城市在阈值内的邻居数
        best_city = -1
        min_count = INF
        for i in range(n):
            count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
            if count <= min_count:
                min_count = count
                best_city = i

        return best_city

7. 最短路径算法选择决策树

需要计算最短路径
  ├── 边权有负数？
  │   ├── 是 → 需要检测负环？
  │   │   ├── 是 → Bellman-Ford（第 n 轮）
  │   │   └── 否 → Bellman-Ford（SPFA 做加速，但非稳定最优）
  │   └── 否 → 继续 ▼
  └── 边权非负 → 需要全源最短路径？
      ├── 是 → V 较小（≤ 100）? → Floyd-Warshall
      │        V 较大？        → 跑 V 次 Dijkstra
      └── 否 → 单源 → Dijkstra（堆优化）

算法	类型	支持负权	支持负环检测	复杂度
BFS	无权图单源	—	—	$O(V+E)$
Dijkstra	带权图单源	否	否	$O((V+E)\log V)$
Bellman-Ford	带权图单源	是	是	$O(VE)$
Floyd-Warshall	全源	是	否	$O(V^3)$

结论 (Conclusion)

本文完成了最短路径算法三部曲：

Dijkstra：贪心 + 优先队列，处理非负权图的最优解，复杂度 $O((V+E)\log V)$。
Bellman-Ford：DP + 边松弛，可处理负权边和检测负环，复杂度 $O(VE)$。
Floyd-Warshall：DP + 三重循环，全源最短路径，复杂度 $O(V^3)$。

三道题目（743、787、1334）各对应一种算法的直接应用，同时引入了惰性删除、松弛轮次控制、上一轮副本等关键实现技巧。

下一篇预览：最小生成树与并查集——Kruskal（边排序 + 并查集）与 Prim（优先队列），以及并查集的两大优化（路径压缩 + 按秩合并）（LeetCode 1584、684）。