C++写一篇dijsktra

Dijkstra算法是一种用于求解最短路径的算法，它的基本思想是从一个起点出发，遍历所有的节点，找到到达每个节点的最短路径。下面我们来看一下Dijkstra算法的具体实现。

1. 初始化

首先，我们需要对算法进行初始化。我们将起点设置为已知距离为0的节点，将所有其他节点的距离设置为无穷大。我们还需要一个列表来记录已经访问过的节点。

2. 选择当前节点

接下来，我们需要选择当前节点。我们从未访问过的节点中选择距离起点最近的节点作为当前节点。我们将当前节点标记为已访问过。

3. 更新距离

现在，我们需要更新所有相邻节点的距离。我们遍历当前节点的所有相邻节点，计算到达这些节点的距离。如果这些距离比当前已知的距离更短，那么我们更新这些节点的距离。

4. 重复

我们重复以上三个步骤，直到所有节点都被访问过为止。最终，我们就可以得到从起点到达每个节点的最短路径。

下面是Dijkstra算法的Python实现：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = []
    heap = [(0, start)]
    
    while heap:
        (cost, current_node) = heapq.heappop(heap)
        
        if current_node in visited:
            continue
        
        visited.append(current_node)
        
        for neighbor, weight in graph[current_node].items():
            distance = cost + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
                
    return distances

这段代码中，我们使用了Python的heapq模块来实现堆排序。我们使用一个字典来表示图，其中每个节点都是一个字典，包含它的相邻节点和它们之间的边权重。我们还定义了一个distances字典来记录每个节点的距离，一个visited列表来记录已经访问过的节点，一个heap列表来进行堆排序。

在主循环中，我们从heap中弹出距离最小的节点。如果这个节点已经被访问过，我们就跳过它。否则，我们将它标记为已访问，并更新它相邻节点的距离。如果发现有更短的路径，我们就更新这些节点的距离，并将它们添加到heap中。

最后，我们返回distances字典，它包含了从起点到达每个节点的最短路径。