Dijkstra算法 python

Dijkstra算法是一种用于求解最短路径问题的算法，它能够找到起点到图中所有其他节点的最短路径。下面是一个使用Python实现Dijkstra算法的示例代码：

import sys

def dijkstra(graph, start):
    # 初始化距离字典，用于存储起点到每个节点的最短距离
    distances = {node: sys.maxsize for node in graph}
    distances[start] = 0  # 起点到自身的距离为0

    # 创建一个集合，用于存储已经找到最短路径的节点
    visited = set()

    while len(visited) < len(graph):
        # 找到当前未访问的节点中距离起点最近的节点
        min_distance = sys.maxsize
        for node in graph:
            if node not in visited and distances[node] < min_distance:
                min_distance = distances[node]
                current_node = node

        # 标记当前节点为已访问
        visited.add(current_node)

        # 更新与当前节点相邻节点的最短距离
        for neighbor in graph[current_node]:
            distance = distances[current_node] + graph[current_node][neighbor]
            if distance < distances[neighbor]:
                distances[neighbor] = distance

    return distances

# 测试代码
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 2, 'B': 1, 'D': 6},
    'D': {'B': 3, 'C': 6}
}

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

print("从节点 {} 到各节点的最短距离:".format(start_node))
for node, distance in distances.items():
    print("到节点 {}: {}".format(node, distance))

这段代码实现了Dijkstra算法，通过传入一个图和起点，可以计算出起点到图中其他节点的最短距离。在示例代码中，我们使用了一个字典来表示图的邻接关系，其中键表示节点，值是另一个字典，表示与该节点相邻的节点及其距离。运行代码后，会输出起点到各个节点的最短距离。

希望能对你有所帮助！如有任何疑问，请随时提问。