Dijsktra算法求到任意两点的最短路径

Dijsktra算法是一种用于求解带权图中单源最短路径的贪心算法。其基本思想是从起点开始，逐步扩大范围，直到覆盖所有节点。在扩大的过程中，每次选择当前距离起点最近的一个节点，并更新与该节点相邻的节点的距离。具体步骤如下：

1.初始化：将起点到各个节点的距离设为正无穷，将起点到自身的距离设为0。

2.选择当前距离起点最近的一个节点，并标记为已访问。

3.更新与该节点相邻的节点的距离：如果经过当前节点到达相邻节点的距离比原来的距离更短，则更新距离。

4.重复步骤2和3，直到所有节点都被访问过。

5.输出起点到各个节点的最短路径。

以下是一个使用Python实现Dijsktra算法的例子：

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': 2, 'C': 4},
    'B': {'C': 1, 'D': 3},
    'C': {'D': 2},
    'D': {'C': 1, 'E': 3},
    'E': {'F': 2},
    'F': {}
}

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

# 输出：{'A': 0, 'B': 2, 'C': 3, 'D': 5, 'E': 8, 'F': inf}