数据结构与算法 / 系统课时
单源最短路径
单源最短路径
单源最短路径要计算一个起点到其他节点的最低总代价。本课聚焦非负权图,使用 Dijkstra 算法、最小堆和前驱表完成距离更新,并还原起点到目标点的具体路径。
学习目标
- 理解松弛操作与“当前最小候选距离”的含义
- 使用最小堆实现 Dijkstra 算法并跳过过期堆项
- 判断非负权前提、不可达节点与复杂度边界
问题定义与算法前提
与 BFS 只统计边数不同,带权图需要累加每条边的权重。Dijkstra 算法适用于所有边权均为非负数的图;只要存在负权边,即使没有负环,也不能直接依赖该算法的贪心结论。
算法把源点距离设为 0,其他节点设为无穷大。最小堆保存尚待处理的候选状态,每次弹出当前已知距离最小的节点,再尝试通过它改进邻居距离。

松弛与过期堆项
若当前节点为 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复杂度与边界
使用邻接表和二叉最小堆时,常写作 ;对连通稀疏图也常简化为 。距离表、前驱表和堆需要 级别的额外空间,具体取决于堆中保留的旧状态数量。
不可达节点的距离保持无穷大,路径应返回空结果。若图中包含负权边,应改用 Bellman-Ford 等能够处理负权的算法,而不是通过调整访问标记勉强修补 Dijkstra。
按自己的节奏,确认真正理解。