dijkstra算法python

Dijkstra算法是一种用于寻找带权重图中从一个起始节点到其他节点的最短路径的算法。下面是一个使用Python实现Dijkstra算法的示例代码：

import heapq

def dijkstra(graph, start):

    # 创建一个字典来存储节点到起始节点的最短距离

    distances = {node: float('infinity') for node in graph}

    distances[start] = 0

    # 使用优先队列（最小堆）来选择下一个要探索的节点

    priority_queue = [(0, start)]

    while priority_queue:

        current_distance, current_node = heapq.heappop(priority_queue)

        # 如果当前距离大于节点距离字典中的值，则跳过

        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(priority_queue, (distance, neighbor))

    return distances

# 示例图的字典表示

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}

}

start_node = 'A'

shortest_distances = dijkstra(graph, start_node)

for node, distance in shortest_distances.items():

print(f'Shortest distance from {start_node} to {node} is {distance}')

这个代码首先创建了一个距离字典来跟踪从起始节点到各个节点的最短距离，然后使用优先队列（最小堆）来选择下一个要探索的节点。在遍历节点时，它会检查是否存在更短的路径，如果有就更新距离字典。最终，它输出从起始节点到其他节点的最短距离