Python Dijkstra算法与优先级队列

Dijkstra最短路径使用heapq优先级队列。优先队列总是取当前最小dist节点。邻接表表示图。O(E log V)复杂度。A*启发式扩展。负权边不能用。路径重建predecessor。

import heapq

def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = [(0, start)]

while queue:
current_dist, node = heapq.heappop(queue)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances

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)]
}

result = dijkstra(graph, 'A')
print(result) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

# 应用：网络路由、地图导航、游戏AI

import sys, math

# A*算法
def astar(graph, start, goal, h):
pass