30 秒速览

  • 无权图：BFS
  • 正权图：Dijkstra
  • 负权图：Bellman-Ford
  • 全点对：Floyd-Warshall
  • 关键点：松弛操作（尝试更新最短距离）

一、直觉建立

最短路径的本质

从一个点到另一个点，找"代价最小"的路径。代价可以是：

  • 边数（无权）
  • 边权之和（有权）
  • 时间、费用等

松弛操作

所有最短路径算法的核心都是松弛：

# 如果通过 u 到 v 更短，就更新
if dist[u] + w(u, v) < dist[v]:
    dist[v] = dist[u] + w(u, v)

算法选择

图的类型算法时间复杂度
无权图BFSO(V + E)
正权图DijkstraO((V + E) log V)
有负权Bellman-FordO(V × E)
全点对FloydO(V³)

二、BFS（无权图）

模板

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, 0)])
    visited = set([start])

    while queue:
        node, dist = queue.popleft()

        if node == end:
            return dist

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1  # 无法到达

典型题目

LC 1091. 二进制矩阵中的最短路径

from collections import deque

def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    n = len(grid)

    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    if n == 1:
        return 1

    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    queue = deque([(0, 0, 1)])
    grid[0][0] = 1

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                if nr == n - 1 and nc == n - 1:
                    return dist + 1

                grid[nr][nc] = 1
                queue.append((nr, nc, dist + 1))

    return -1

三、Dijkstra（正权图）

核心思想

每次选择距离最小的未确定节点，用它来松弛邻居。

模板

import heapq

def dijkstra(graph, start, n):
    # graph: {u: [(v, weight), ...]}
    dist = [float('inf')] * n
    dist[start] = 0

    # (距离, 节点)
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:  # 已找到更短的
            continue

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

为什么 Dijkstra 不能处理负权？

Dijkstra 假设：已确定的节点不会被更新。 有负权边时，这个假设不成立。

四、典型例题

例题 1：LC 743. 网络延迟时间

题目：从节点 k 发送信号，多久后所有节点都能收到？

示例：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

Dijkstra

import heapq
from collections import defaultdict

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    # 构建邻接表
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    # Dijkstra
    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    # 结果
    max_dist = max(dist[1:])
    return max_dist if max_dist != float('inf') else -1

复杂度：时间 O(E log V)，空间 O(V + E)

例题 2：LC 1514. 概率最大的路径

题目：找从 start 到 end 概率最大的路径。

思路

把概率相乘变成对数相加，或者直接用最大堆。

import heapq
from collections import defaultdict

def maxProbability(n: int, edges: list[list[int]], succProb: list[float],
                   start: int, end: int) -> float:
    # 构建邻接表
    graph = defaultdict(list)
    for (u, v), prob in zip(edges, succProb):
        graph[u].append((v, prob))
        graph[v].append((u, prob))

    # Dijkstra 变体：最大概率
    probs = [0.0] * n
    probs[start] = 1.0
    pq = [(-1.0, start)]  # 负号实现最大堆

    while pq:
        neg_prob, u = heapq.heappop(pq)
        prob = -neg_prob

        if prob < probs[u]:
            continue

        for v, p in graph[u]:
            new_prob = prob * p
            if new_prob > probs[v]:
                probs[v] = new_prob
                heapq.heappush(pq, (-new_prob, v))

    return probs[end]

例题 3：LC 787. K 站中转内最便宜的航班

题目：从 src 到 dst，最多经过 k 个中转站，求最低价格。

Bellman-Ford 思想

限制中转次数 = 限制松弛的轮数。

def findCheapestPrice(n: int, flights: list[list[int]],
                      src: int, dst: int, k: int) -> int:
    # Bellman-Ford 最多 k+1 轮
    prices = [float('inf')] * n
    prices[src] = 0

    for _ in range(k + 1):
        # 每轮用上一轮的结果更新
        temp = prices[:]

        for u, v, w in flights:
            if prices[u] != float('inf'):
                temp[v] = min(temp[v], prices[u] + w)

        prices = temp

    return prices[dst] if prices[dst] != float('inf') else -1

复杂度：时间 O(k × E)，空间 O(V)

例题 4：LC 1334. 阈值距离内邻居最少的城市

题目：找哪个城市在距离阈值内的邻居最少。

Floyd-Warshall

def findTheCity(n: int, edges: list[list[int]], distanceThreshold: int) -> int:
    # 初始化距离矩阵
    dist = [[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] = w
        dist[v][u] = w

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

    # 找答案
    min_neighbors = n
    result = 0

    for i in range(n):
        neighbors = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
        if neighbors < min_neighbors or (neighbors == min_neighbors and i > result):
            min_neighbors = neighbors
            result = i

    return result

复杂度：时间 O(n³)，空间 O(n²)

例题 5：LC 1631. 最小体力消耗路径

题目：从左上到右下，路径的体力消耗 = 路径上相邻格子高度差的最大值，求最小消耗。

二分 + BFS/DFS

import heapq

def minimumEffortPath(heights: list[list[int]]) -> int:
    m, n = len(heights), len(heights[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # Dijkstra 变体：记录路径上的最大高度差
    effort = [[float('inf')] * n for _ in range(m)]
    effort[0][0] = 0
    pq = [(0, 0, 0)]  # (effort, row, col)

    while pq:
        e, r, c = heapq.heappop(pq)

        if e > effort[r][c]:
            continue

        if r == m - 1 and c == n - 1:
            return e

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if 0 <= nr < m and 0 <= nc < n:
                new_effort = max(e, abs(heights[nr][nc] - heights[r][c]))
                if new_effort < effort[nr][nc]:
                    effort[nr][nc] = new_effort
                    heapq.heappush(pq, (new_effort, nr, nc))

    return 0

五、算法对比

Dijkstra vs Bellman-Ford

特性DijkstraBellman-Ford
边权只能正权可以负权
时间O(E log V)O(V × E)
负环不能检测可以检测
实现优先队列多轮松弛

Floyd-Warshall

  • 全点对最短路径
  • 可以处理负权（不能有负环）
  • 时间 O(V³)，适合小图
# Floyd 模板
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

六、常见错误与陷阱

错误 1：Dijkstra 标记时机

# 错误：出队时标记
while pq:
    d, u = heapq.heappop(pq)
    visited.add(u)  # 可能有更短的路径被跳过

# 正确：用距离比较
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:  # 已找到更短的
        continue

错误 2：负权用 Dijkstra

# 有负权边时，Dijkstra 结果不正确
# 必须用 Bellman-Ford

错误 3：Bellman-Ford 轮数

# 无负环时，n-1 轮足够
# 检测负环需要第 n 轮
for _ in range(n - 1):
    # 松弛
for edge in edges:
    if dist[u] + w < dist[v]:
        # 有负环

错误 4：Floyd 初始化

# 对角线必须是 0
for i in range(n):
    dist[i][i] = 0

七、复盘清单

触发信号

  • 最短路径/最少步数
  • 从 A 到 B 的最小代价
  • 全点对距离

算法选择

  • 无权/权重相同 → BFS
  • 正权单源 → Dijkstra
  • 负权/限制中转 → Bellman-Ford
  • 全点对 → Floyd

实现检查

  • 优先队列用法
  • 松弛操作正确
  • 初始化正确
  • 返回值处理

八、题目清单

BFS 最短路径

题号题目难度考点
1091二进制矩阵最短路径Medium8 方向 BFS
127单词接龙HardBFS

Dijkstra

题号题目难度考点
743网络延迟时间Medium基础 Dijkstra
1514概率最大路径Medium最大堆
1631最小体力消耗Medium路径最值

Bellman-Ford

题号题目难度考点
787K 站中转最便宜航班Medium限制轮数

Floyd

题号题目难度考点
1334阈值距离内邻居最少Medium全点对