邻接表的dijkstra算法

邻接表的Dijkstra算法是一种用于解决有权图中最短路径问题的算法。它使用邻接表作为图的存储结构，并采用贪心算法的策略来找到从起始点到其他各节点的最短路径。

下面是邻接表的Dijkstra算法的步骤：

1. 创建一个空的最短路径集合，用于存储已经找到最短路径的节点。
2. 创建一个距离数组，用于存储起始点到每个节点的最短距离。将起始点的距离设置为0，其他节点的距离设置为无穷大。
3. 创建一个优先队列（最小堆），用于选择下一个要访问的节点。将起始点加入优先队列。
4. 循环执行以下步骤，直到优先队列为空：
- 从优先队列中取出距离最小的节点，将其加入最短路径集合。
- 遍历该节点的邻接节点：
- 如果该邻接节点不在最短路径集合中：
- 计算从起始点经过当前节点到该邻接节点的距离。
- 如果该距离小于该邻接节点的当前最短距离，则更新该邻接节点的最短距离。
- 将该邻接节点加入优先队列。
5. 最终，距离数组中存储的就是起始点到每个节点的最短距离。

下面是一个示例代码，演示了如何使用邻接表的Dijkstra算法来找到最短路径：

import heapq

def dijkstra(graph, start):
    # 创建距离数组，初始化为无穷大
    distances = {node: float('inf') for node in graph}
    # 将起始点的距离设置为0
    distances[start] = 0
    # 创建优先队列，并将起始点加入队列
    queue = [(0, start)]

    while queue:
        # 从优先队列中取出距离最小的节点
        current_distance, current_node = heapq.heappop(queue)

        # 如果当前节点已经在最短路径集合中，则跳过
        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(queue, (distance, neighbor))

    return distances

# 示例图的邻接表表示
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6},
    'D': {'B': 3, 'C': 2, 'E': 4, 'F': 2},
    'E': {'C': 6, 'D': 4, 'F': 6},
    'F': {'D': 2, 'E': 6}
}

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

这段代码演示了一个示例图的邻接表表示，并使用Dijkstra算法找到从起始点A到其他各节点的最短距离。