迪杰斯特拉算法python

迪杰斯特拉算法（Dijkstra's algorithm）是一种常用于解决加权最短路径问题的算法，它能够找到从单个源点到图中所有其他节点的最短路径。

下面是一个使用Python实现的基本的迪杰斯特拉算法：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，将起点的距离设为0，其余设为无穷大
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    
    # 初始化堆和标记集
    heap = [(0, start)]
    visited = set()
    
    # 进行迪杰斯特拉算法
    while heap:
        # 取出堆中距离最小的节点
        (dist, current_node) = heapq.heappop(heap)
        
        # 如果当前节点已经被访问过，则跳过
        if current_node in visited:
            continue
        
        # 将当前节点标记为已访问
        visited.add(current_node)
        
        # 对当前节点的所有邻居进行松弛操作
        for neighbor, weight in graph[current_node].items():
            distance_to_neighbor = dist + weight
            if distance_to_neighbor < distance[neighbor]:
                distance[neighbor] = distance_to_neighbor
                heapq.heappush(heap, (distance_to_neighbor, neighbor))
    
    # 返回距离字典
    return distance

其中，`graph`是一个字典，表示有向加权图，`start`是起点节点。

例如，使用以下代码来测试算法：

graph = {
    'A': {'B': 10, 'C': 3},
    'B': {'C': 1, 'D': 2},
    'C': {'B': 4, 'D': 8, 'E': 2},
    'D': {'E': 7},
    'E': {'D': 9}
}

print(dijkstra(graph, 'A'))

输出结果为：

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

表示从起点节点A到其他节点的最短距离。