Dijkstra最短路径算法实现代码

当然，以下是一个使用Python实现的Dijkstra最短路径算法的简单示例。这个示例使用了优先队列（通过`heapq`模块实现）来优化查找下一个最近顶点的过程。

import heapq

def dijkstra(graph, start):
    # 初始化距离表，所有距离都设为无穷大，除了起点到自身的距离为0
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    # 优先队列，用于存储(距离, 顶点)对
    priority_queue = [(0, start)]

    while priority_queue:
        # 取出当前距离最小的顶点
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # 顶点距离已经是最小，无需再处理
        if current_distance > distances[current_vertex]:
            continue

        # 遍历当前顶点的所有邻居
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 只有在找到更短的路径时才进行更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 示例图（使用邻接表表示）
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'开始的最短路径
start_vertex = 'A'
shortest_paths = dijkstra(graph, start_vertex)
print(shortest_paths)

这段代码首先定义了`dijkstra`函数，它接受一个图（以邻接表形式）和一个起始顶点作为输入，并返回从起始顶点到图中所有其他顶点的最短距离。图中每个顶点都是一个字典的键，而每个键对应的值又是一个字典，表示从该顶点出发可以到达的其他顶点和相应的边的权重。

然后，我们定义了一个示例图`graph`，并使用`dijkstra`函数计算从顶点'A'开始的最短路径，并将结果打印出来。

注意：在实际应用中，图的表示和存储方式可能会有所不同，但这个示例应该能够提供一个清晰的Dijkstra算法实现框架。