C++求迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra's algorithm）是一种用于计算单源最短路径的算法。它通过从起始点开始逐步扩展已找到的最短路径，直到到达目标点或遍历完所有节点，从而确定起始点到其他节点的最短路径。

以下是迪杰斯特拉算法的步骤：

1. 创建一个节点集合，存储所有的节点。
2. 初始化起始点的最短路径为0，将其它节点的最短路径设置为无穷大。
3. 选择一个未访问过且最短路径最小的节点作为当前节点。
4. 遍历当前节点的所有邻居节点，更新其最短路径值。如果经过当前节点到达邻居节点的路径比已记录的最短路径更短，则更新最短路径。
5. 标记当前节点为已访问。
6. 重复步骤3-5，直到所有节点都被标记为已访问或者找到了目标节点。
7. 返回起始点到每个节点的最短路径。

以下是一个示例代码实现：

import heapq

def dijkstra(graph, start):
    # 创建一个堆来存储节点和到起始点的距离
    heap = [(0, start)]
    # 创建一个字典来存储每个节点的最短距离
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    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': 2},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 2, 'B': 1, 'D': 1},
    'D': {'B': 3, 'C': 1}
}

start_node = 'A'
distances = dijkstra(graph, start_node)

for node, distance in distances.items():
    print(f'Shortest distance from {start_node} to {node}: {distance}')

# 相关问题: