最短路径dijkstra算法python解法

以下是使用Python实现Dijkstra算法求解最短路径的示例代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，将起点到起点的距离设为0，其余为无穷大
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    
    # 初始化堆和visited集合
    heap = [(0, start)]
    visited = set()
    
    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`是一个字典，表示图的邻接表，`start`是起点。字典中的每个键表示一个节点，对应的值是一个字典，表示该节点的所有邻居节点及其边权重。

以下是一个示例图及其邻接表：

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}
}

使用Dijkstra算法求解起点`A`到其它节点的最短路径：

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

输出结果为：

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

表示起点`A`到各个节点的最短距离。