Dijkstra最短路径算法 简单代码

以下是一个简单的Python代码示例，用于实现Dijkstra最短路径算法：

import heapq

def dijkstra(graph, start):
    # 初始化距离和前驱节点
    dist = {vertex: float('inf') for vertex in graph}
    dist[start] = 0
    prev = {vertex: None for vertex in graph}

    # 使用堆优化的Dijkstra算法
    pq = [(0, start)]
    while pq:
        (distance, current_vertex) = heapq.heappop(pq)
        if distance > dist[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            new_distance = dist[current_vertex] + weight
            if new_distance < dist[neighbor]:
                dist[neighbor] = new_distance
                prev[neighbor] = current_vertex
                heapq.heappush(pq, (new_distance, neighbor))

    return dist, prev

以上代码实现了Dijkstra最短路径算法，输入参数为一个带权重的邻接表（graph）和起始节点（start）。输出结果为一个字典，包含每个节点到起始节点的最短距离（dist）和前驱节点（prev）。该算法使用堆优化以提高效率。