Dijkstra算法的Python实现
Dijkstra算法是一种用于在加权图中找到单源最短路径的经典算法,下面我将提供一个完整的Python实现，包括优先队列优化版本。
基础实现（使用优先队列）
import heapq
def dijkstra(graph, start):
"""
使用Dijkstra算法计算从起始节点到所有其他节点的最短路径
参数:
graph: 图的邻接表表示，格式为 {节点: {邻居: 权重}}
start: 起始节点
返回:
distances: 从起始节点到所有其他节点的最短距离字典
previous: 记录最短路径中每个节点的前驱节点字典
"""
# 初始化距离字典，所有节点初始距离为无穷大
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# 初始化前驱字典
previous = {node: None for node in graph}
# 使用优先队列（最小堆），存储(距离, 节点)的元组
priority_queue = [(0, start)]
while priority_queue:
# 取出当前距离最小的节点
current_distance, current_node = heapq.heappop(priority_queue)
# 如果当前距离大于已知距离，跳过
if current_distance > distances[current_node]:
continue
# 遍历当前节点的所有邻居
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 如果找到更短的路径，更新距离和前驱
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_node
heapq.heappush(priority_queue, (distance, neighbor))
return distances, previous
示例使用
# 示例图
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}
}
# 计算从'A'出发的最短路径
distances, previous = dijkstra(graph, 'A')
print("最短距离:")
for node in distances:
print(f"从 {previous[node] if previous[node] else '起点'} 到 {node}: {distances[node]}")
# 打印从'A'到'D'的路径
def get_path(previous, end):
path = []
while end is not None:
path.append(end)
end = previous[end]
return path[::-1]
print("\n从A到D的路径:", get_path(previous, 'D'))
带有路径重建的完整实现
import heapq
def dijkstra_with_path(graph, start):
"""
带路径重建功能的Dijkstra算法实现
参数:
graph: 图的邻接表表示
start: 起始节点
返回:
distances: 最短距离字典
paths: 从起始节点到所有节点的路径字典
"""
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# 存储路径
paths = {node: [] for node in graph}
paths[start] = [start]
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
paths[neighbor] = paths[current_node] + [neighbor]
heapq.heappush(priority_queue, (distance, neighbor))
return distances, paths
# 使用示例
distances, paths = dijkstra_with_path(graph, 'A')
print("\n完整路径重建:")
for node in paths:
print(f"从A到{node}的路径: {' -> '.join(paths[node])}, 距离: {distances[node]}")
算法复杂度分析
-
时间复杂度：O((V + E) log V)，其中V是顶点数，E是边数
- 使用优先队列（最小堆）实现
- 每个顶点最多被处理一次
- 每条边最多被检查一次
- 堆操作的时间复杂度为O(log V)
-
空间复杂度：O(V)
- 存储距离和前驱信息需要O(V)空间
- 优先队列最多包含O(V)个元素
注意事项
- Dijkstra算法不能处理带有负权边的图
- 对于负权边,应使用Bellman-Ford算法
- 如果图中存在负权环,Bellman-Ford算法可以检测到，而Dijkstra算法会给出错误结果
这个实现是Dijkstra算法的高效版本,适用于大多数实际应用场景。
