python实现迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra算法）是一种用于解决带权有向图最短路径问题的算法，其主要思想是利用贪心策略，先找到距离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其他所有顶点的最短路径。以下是Python实现迪杰斯特拉算法的代码：

import heapq

def dijkstra(graph, start):
    """Dijkstra算法求解最短路径"""
    # 初始化距离和前驱字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    
    # 初始化堆，将起点加入堆中
    heap = [(0, start)]
    
    while heap:
        # 从堆中取出距离最小的顶点
        (distance, current) = heapq.heappop(heap)
        
        # 如果当前顶点已经处理过，则跳过当前循环
        if distance > dist[current]:
            continue
            
        # 遍历当前顶点的邻居，更新其距离和前驱字典
        for neighbor, weight in graph[current].items():
            new_distance = dist[current] + weight
            if new_distance < dist[neighbor]:
                dist[neighbor] = new_distance
                prev[neighbor] = current
                heapq.heappush(heap, (new_distance, neighbor))
    
    return dist, prev

# 示例
graph = {
    'A': {'B': 10, 'C': 3},
    'B': {'C': 1, 'D': 2},
    'C': {'B': 4, 'D': 8, 'E': 2},
    'D': {'E': 7},
    'E': {'D': 9}
}
dist, prev = dijkstra(graph, 'A')
print(dist)
print(prev)

输出结果为：

{'A': 0, 'B': 7, 'C': 3, 'D': 9, 'E': 5}
{'A': None, 'B': 'C', 'C': 'A', 'D': 'B', 'E': 'C'}

其中，`dist`字典表示起点到各个顶点的最短距离，`prev`字典表示最短路径上各个顶点的前驱节点。可以根据`prev`字典来还原出从起点到其他顶点的最短路径。