d*lite 算法求解最优路径 python

dijkstra算法是一种用于寻找图中两点间最短路径的经典算法，尤其适用于带权重的无负权边的图。在Python中，我们可以使用heapq库配合字典数据结构来实现Dijkstra算法。

首先，创建一个空字典存储已知节点到起点的距离，并将所有节点标记为未访问。然后，从起始节点开始，将其距离设为0，其余为无穷大。接下来，维护一个最小堆，堆顶始终是当前找到的最短路径源节点。每次从堆顶取出节点，更新与其相邻节点的距离，如果新的距离更短，就更新这个节点并调整堆。

以下是简化版的Python Dijkstra算法实现：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        current_distance, current_node = heapq.heappop(heap)
        
        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
                heapq.heappush(heap, (distance, neighbor))
                
    return distances

# 使用示例
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'D': 2},
    'C': {'A': 1, 'D': 4},
    'D': {'B': 2, 'C': 4, 'E': 8},
    'E': {'D': 8}
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(f"Shortest paths from {start_node}: {shortest_paths}")