数据结构与算法 / 系统课时

单源最短路径

单源最短路径

单源最短路径要计算一个起点到其他节点的最低总代价。本课聚焦非负权图,使用 Dijkstra 算法、最小堆和前驱表完成距离更新,并还原起点到目标点的具体路径。

学习目标

  • 理解松弛操作与“当前最小候选距离”的含义
  • 使用最小堆实现 Dijkstra 算法并跳过过期堆项
  • 判断非负权前提、不可达节点与复杂度边界

问题定义与算法前提

与 BFS 只统计边数不同,带权图需要累加每条边的权重。Dijkstra 算法适用于所有边权均为非负数的图;只要存在负权边,即使没有负环,也不能直接依赖该算法的贪心结论。

算法把源点距离设为 0,其他节点设为无穷大。最小堆保存尚待处理的候选状态,每次弹出当前已知距离最小的节点,再尝试通过它改进邻居距离。

Dijkstra 松弛与最小堆流程

松弛与过期堆项

若当前节点为 u,邻居为 v,边权为 w,松弛操作比较 distance[u] + w 与 distance[v]。前者更小时,就更新 distance[v],记录 previous[v] = u,并把新状态压入最小堆。

Python 标准堆不提供高效的“修改已有元素优先级”操作。常用做法是直接压入新状态,保留旧状态;旧状态以后弹出时,若它的距离不等于距离表中的最新值,就跳过。这样避免在线性时间内查找和删除堆项。

当只关心一个目标节点时,该目标以最新距离从堆中弹出后即可提前结束。此前仅仅“发现”目标并不代表距离已经最终确定。

主示例:距离表与路径还原

python
import heapq
from math import inf
from typing import Optional

def dijkstra(
    graph: dict[str, list[tuple[str, int]]],
    start: str,
) -> tuple[dict[str, float], dict[str, Optional[str]]]:
    if start not in graph:
        raise ValueError("源点必须存在于图中")

    for edges in graph.values():
        if any(weight < 0 for _, weight in edges):
            raise ValueError("Dijkstra 不支持负权边")

    distances = {vertex: inf for vertex in graph}
    previous: dict[str, Optional[str]] = {
        vertex: None for vertex in graph
    }
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        current_distance, current = heapq.heappop(heap)

        # 跳过已被更短路径替代的旧堆项
        if current_distance != distances[current]:
            continue

        for neighbor, weight in graph[current]:
            new_distance = current_distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                previous[neighbor] = current
                heapq.heappush(heap, (new_distance, neighbor))

    return distances, previous

def restore_path(
    previous: dict[str, Optional[str]],
    distances: dict[str, float],
    target: str,
) -> Optional[list[str]]:
    if target not in distances or distances[target] == inf:
        return None

    path = []
    current: Optional[str] = target
    while current is not None:
        path.append(current)
        current = previous[current]

    return list(reversed(path))

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 1), ("D", 5)],
    "C": [("B", 1), ("D", 8), ("E", 10)],
    "D": [("E", 2)],
    "E": [],
}

distances, previous = dijkstra(graph, "A")
path = restore_path(previous, distances, "E")

print("最短距离:", distances)
print("A 到 E 的路径:", path)
print("A 到 E 的距离:", distances["E"])

预期输出:

text
最短距离: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}
A 到 E 的路径: ['A', 'C', 'B', 'D', 'E']
A 到 E 的距离: 10

复杂度与边界

使用邻接表和二叉最小堆时,常写作 O((V+E)log⁡V)O((V+E)\log V);对连通稀疏图也常简化为 O(Elog⁡V)O(E\log V)。距离表、前驱表和堆需要 O(V+E)O(V+E) 级别的额外空间,具体取决于堆中保留的旧状态数量。

不可达节点的距离保持无穷大,路径应返回空结果。若图中包含负权边,应改用 Bellman-Ford 等能够处理负权的算法,而不是通过调整访问标记勉强修补 Dijkstra。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

单源最短路径

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通