迪杰斯特拉(Dijkstra's )算法代码模板

迪杰斯特拉(Dijkstra's)算法是一种用于寻找图中两点之间最短路径的经典算法，通常用于解决单源最短路径问题。以下是使用Python实现的一个基本模板：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    heap = [(0, start)]  # 优先级队列，元素包含距离和节点
    visited = set()

    while heap:
        current_distance, current_node = heapq.heappop(heap)

        if current_node not in visited:
            visited.add(current_node)
            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': 1, 'C': 4},
    'B': {'A': 1, 'D': 5},
    'C': {'A': 4, 'D': 8, 'E': 3},
    'D': {'B': 5, 'C': 8, 'E': 2},
    'E': {'C': 3, 'D': 2}
}

shortest_paths = dijkstra(graph, 'A')
print(shortest_paths)  # 输出从'A'到其他各点的最短距离

在这个模板中，`graph`是一个字典，键是图中的节点，值是另一个字典，表示与该节点相邻的节点及其边的权重。算法通过维护一个优先级队列来不断更新每个节点的最短距离，并遍历整个图直到找到所有最短路径。