Dijkstra最短路径使用heapq优先级队列。优先队列总是取当前最小dist节点。邻接表表示图。O(E log V)复杂度。A*启发式扩展。负权边不能用。路径重建predecessor。import heapqdef dijkstra(graph, start):distances {node: float(inf) for node in graph}distances[start] 0queue [(0, start)]while queue:current_dist, node heapq.heappop(queue)if current_dist distances[node]:continuefor neighbor, weight in graph[node]:distance current_dist weightif distance distances[neighbor]:distances[neighbor] distanceheapq.heappush(queue, (distance, neighbor))return distancesgraph {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}# 应用网络路由、地图导航、游戏AIimport sys, math# A*算法def astar(graph, start, goal, h):pass