狄克斯特拉算法python

可以使用以下python代码实现狄克斯特拉算法：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        (current_distance, current_node) = heapq.heappop(heap)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
                
    return distances

这个函数的参数`graph`表示一个字典，键是节点名称，值是另一个字典，其键是从该节点可达的节点名称，值是连接这两个节点的边的权重。`start`是起始节点的名称。

例如，如果有以下图形数据：

graph = {
    'A': {'B': 7, 'C': 9, 'F': 14},
    'B': {'A': 7, 'C': 10, 'D': 15},
    'C': {'A': 9, 'B': 10, 'D': 11, 'F': 2},
    'D': {'B': 15, 'C': 11, 'E': 6},
    'E': {'D': 6, 'F': 9},
    'F': {'A': 14, 'C': 2, 'E': 9}
}

start = 'A'

调用`dijkstra(graph, start)`函数将返回一个字典，表示从起始节点到其余节点的最短距离，例如：

{'A': 0, 'B': 7, 'C': 9, 'D': 20, 'E': 20, 'F': 11}