Python实现Dijkstra算法：图论最短路径的基石与实战指南92

在计算机科学和日常生活中，我们经常遇到寻找“最短路径”的问题，无论是导航系统规划从A点到B点的最优路线，还是网络路由器选择数据包传输的最快路径。Dijkstra（迪克斯特拉）算法就是解决这类问题最经典、最广泛使用的算法之一。作为一名专业的程序员，熟练掌握Dijkstra算法及其Python实现，是你在图论和算法领域的重要技能。

本文将深入探讨Dijkstra算法的核心思想、工作原理、Python代码实现、复杂度分析、应用场景及局限性，旨在为你提供一个全面而实用的Dijkstra算法学习指南。

一、Dijkstra算法的核心概念与思想

Dijkstra算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出，主要用于解决“单源最短路径”问题。这意味着它能从图中一个指定的起始节点出发，找到到达所有其他节点的最短路径。

1. 基本概念

图 (Graph)：由一组节点（或顶点，Vertex）和连接这些节点的边（Edge）组成的数据结构。在Dijkstra算法中，边通常带有权重（Weight），表示从一个节点到另一个节点的“代价”或“距离”。

最短路径 (Shortest Path)：在有权图中，从一个节点到另一个节点的路径中，所有边权重之和最小的路径。

单源最短路径 (Single-Source Shortest Path)：从图中一个特定的“源节点”出发，寻找其到图中所有其他可达节点的各自的最短路径。

非负权重 (Non-Negative Weights)：Dijkstra算法的一个关键前提是图中所有边的权重都必须是非负数。如果图中存在负权边，Dijkstra算法将无法保证得到正确结果，此时通常需要使用Bellman-Ford算法或SPFA算法。

2. 算法思想：贪心策略

Dijkstra算法采用的是一种“贪心”策略。它的基本思想是：从源节点开始，逐步探索和扩展已知的最短路径。它维护一个集合，存储已经确定最短路径的节点，并不断从“未确定最短路径”的节点中选择一个距离源节点最近的节点，将其加入到已确定集合中，并更新其邻居节点到源节点的距离。这个过程不断重复，直到所有节点的最短路径都被找到。

用更直观的方式理解：想象你在一个城市里寻找从家到各个地点的最短路线。Dijkstra算法会每次都选择“目前看起来”离家最近的那个未访问地点，然后检查通过这个地点能否到达其邻居地点，并且路径更短。如果是，就更新邻居地点的最短距离。

二、Dijkstra算法的详细步骤

为了更好地理解Dijkstra算法，我们可以将其分解为以下几个核心步骤：

初始化：

创建一个距离字典（或数组），`distances`，用于存储从源节点到每个节点的当前最短距离。将源节点到自身的距离设为0，到其他所有节点的距离设为“无穷大”（表示目前不可达）。
创建一个优先队列（Min-Priority Queue），`priority_queue`，用于存储待访问的节点，并根据它们到源节点的距离进行排序。优先队列中存储的元素通常是 `(距离, 节点)` 的元组。初始时，将 `(0, 源节点)` 加入队列。
创建一个访问集合，`visited`，用于记录已经确定最短路径的节点，防止重复处理。

迭代搜索：

当优先队列非空时，重复以下操作：
从优先队列中取出（弹出）距离源节点最近的节点 `(current_distance, current_node)`。
如果 `current_node` 已经在 `visited` 集合中，则跳过此次循环（因为我们已经找到了到达它的最短路径）。
将 `current_node` 添加到 `visited` 集合中，表示其最短路径已确定。
松弛操作 (Relaxation)： 遍历 `current_node` 的所有邻居 `neighbor`：

计算从源节点经过 `current_node` 到 `neighbor` 的新路径距离：`new_distance = current_distance + weight(current_node, neighbor)`。
如果 `new_distance` 小于 `distances[neighbor]`（即当前已知的从源节点到 `neighbor` 的最短距离），则更新 `distances[neighbor]` 为 `new_distance`。
同时，将 `(new_distance, neighbor)` 加入到优先队列中。

完成：当优先队列为空时，算法结束。`distances` 字典中存储的就是从源节点到所有可达节点的最短距离。

三、Dijkstra算法的Python代码实现

在Python中实现Dijkstra算法，我们可以利用内置的`heapq`模块作为优先队列，以及字典来表示图的邻接列表。

1. 图的表示

我们通常使用邻接列表来表示图。对于有权图，邻接列表的每个元素可以是一个元组 `(邻居节点, 权重)`。这里我们使用 `defaultdict(list)` 来简化图的构建。```python
import heapq
import sys
from collections import defaultdict
# 图的表示: 邻接列表
# graph = {
# 'A': [('B', 1), ('C', 4)],
# 'B': [('A', 1), ('C', 2), ('D', 5)],
# 'C': [('A', 4), ('B', 2), ('D', 1)],
# 'D': [('B', 5), ('C', 1)]
# }
# 使用defaultdict方便添加边
graph = defaultdict(list)
def add_edge(u, v, weight):
"""添加一条从u到v，权重为weight的边"""
graph[u].append((v, weight))
# 如果是无向图，则需要添加反向边
# graph[v].append((u, weight))
```

2. Dijkstra算法函数

```python
def dijkstra(graph, start_node):
"""
实现Dijkstra算法，计算从start_node到图中所有其他节点的最短路径。
Args:
graph (dict): 图的邻接列表表示，例如 { 'A': [('B', 1), ('C', 4)], ... }
start_node (str): 起始节点
Returns:
dict: 存储从start_node到每个节点的最短距离，例如 { 'A': 0, 'B': 1, 'C': 3, 'D': 4 }
如果某个节点不可达，则其距离为。
"""
# 1. 初始化
# distances 字典存储从start_node到每个节点的最短距离
# 初始时，所有节点的距离为无穷大，源节点为0
distances = {node: for node in graph}
distances[start_node] = 0
# priority_queue 是一个最小堆，存储 (距离, 节点) 元组
# heapq 模块实现了一个最小堆队列，每次弹出距离最小的节点
priority_queue = [(0, start_node)]
# visited 集合存储已经确定最短路径的节点
visited = set()
# 2. 迭代搜索
while priority_queue:
# 从优先队列中取出距离最小的节点
current_distance, current_node = (priority_queue)
# 如果当前节点已经访问过，说明我们已经找到过它的最短路径
# 且由于优先队列的特性，此时弹出的距离肯定不会比之前的小（否则会先弹出更小的）
# 所以直接跳过
if current_node in visited:
continue
# 将当前节点标记为已访问，表示其最短路径已确定
(current_node)
# 遍历当前节点的所有邻居
for neighbor, weight in (current_node, []): # 使用.get处理没有出边的节点
# 计算从start_node经过current_node到neighbor的新路径距离
new_distance = current_distance + weight
# 松弛操作：如果新路径更短，则更新距离
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
# 将更新后的邻居及其新距离加入优先队列
(priority_queue, (new_distance, neighbor))
return distances
```

3. 示例用法

```python
if __name__ == "__main__":
# 构建一个示例图 (有向图)
add_edge('A', 'B', 1)
add_edge('A', 'C', 4)
add_edge('B', 'C', 2)
add_edge('B', 'D', 5)
add_edge('C', 'D', 1)
add_edge('D', 'E', 3)
add_edge('E', 'F', 2)
add_edge('C', 'F', 6)
# 确保所有节点都被包含在distances字典中，即使它们没有出边
# 这一步很重要，因为 distances 初始化时需要知道所有节点
all_nodes = set(())
for neighbors in ():
for neighbor, _ in neighbors:
(neighbor)

# 重新构建一个完整的图，包含所有节点
full_graph = {node: (node, []) for node in all_nodes}
# 从节点'A'开始执行Dijkstra算法
start_node = 'A'
shortest_paths = dijkstra(full_graph, start_node)
print(f"从节点 {start_node} 到其他节点的最短路径:")
for node, distance in ():
if distance == :
print(f" 到 {node}: 不可达")
else:
print(f" 到 {node}: {distance}")
print("--- 另一个示例 (无向图) ---")
graph2 = defaultdict(list)
add_edge = lambda u, v, w: (graph2[u].append((v, w)), graph2[v].append((u, w))) # 定义一个添加无向边的匿名函数
add_edge('S', 'A', 6)
add_edge('S', 'B', 2)
add_edge('A', 'E', 1)
add_edge('B', 'A', 3)
add_edge('B', 'C', 5)
add_edge('C', 'D', 5)
add_edge('E', 'D', 8)
add_edge('C', 'E', 2)
all_nodes_2 = set(())
for neighbors in ():
for neighbor, _ in neighbors:
(neighbor)
full_graph2 = {node: (node, []) for node in all_nodes_2}
start_node2 = 'S'
shortest_paths2 = dijkstra(full_graph2, start_node2)
print(f"从节点 {start_node2} 到其他节点的最短路径:")
for node, distance in ():
if distance == :
print(f" 到 {node}: 不可达")
else:
print(f" 到 {node}: {distance}")
```

四、复杂度分析

Dijkstra算法的效率主要取决于其优先队列的实现方式。

时间复杂度：

初始化：O(V) (V为节点数)。
主循环：每个节点最多被弹出优先队列一次（当其最短路径被确定时）。每次弹出操作（`heappop`）的时间复杂度是 O(log P)，其中 P 是优先队列中元素的数量。在最坏情况下，P 可以达到 O(E) (E为边数)，或 O(V) (如果每个节点只入队一次)。
松弛操作：每条边最多被检查一次。对每条边进行松弛操作时，可能伴随一次优先队列的插入操作（`heappush`），其时间复杂度也是 O(log P)。
综合来看，使用二叉堆（Python的`heapq`模块）实现的优先队列，其时间复杂度为 O(E log V) 或 O((V + E) log V)。这是因为每个节点最多被处理一次，每处理一个节点，会遍历其所有出边，对每条边进行一次可能的优先队列操作。由于 `P

2025-11-21

---

下一篇：Python `re` 模块深度解析：高效字符串匹配与处理权威指南