python dijkstra求单源最短路径

Dijkstra算法是一种经典的单源最短路径算法，它可以在有向图或者无向图中求出一个固定源点到其他所有点的最短路径。

以下是使用Python实现Dijkstra算法的示例代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和visited集合
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    visited = set()

    # 初始化堆队列
    heap = [(0, start)]

    while heap:
        # 从堆队列中取出距离最小的节点
        current_distance, current_vertex = heapq.heappop(heap)

        # 如果这个节点已经被访问过，则跳过
        if current_vertex in visited:
            continue

        # 将这个节点标记为已访问
        visited.add(current_vertex)

        # 对于每一个邻居节点，计算距离
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 如果新的距离比之前的距离更短，则更新距离
            if distance < distances[neighbor]:
                distances[neighbor] = distance

                # 将新的距离和邻居节点加入堆队列
                heapq.heappush(heap, (distance, neighbor))

    return distances

其中，graph是一个字典类型的变量，用来表示图的邻接关系，如下所示：

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

这个图表示了四个节点之间的邻接关系，其中节点之间的边权重分别为：

- A -> B：1
- A -> C：4
- B -> C：2
- B -> D：5
- C -> D：1

假设我们要求从节点A到其他所有节点的最短路径，我们可以调用dijkstra函数：

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

运行结果为：

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

这表示从节点A到其他所有节点的最短路径分别为：

- A -> A：0
- A -> B：1
- A -> C：3
- A -> D：4

这就是Dijkstra算法的基本思想和实现方法。