迪杰斯特拉算法代码python

迪杰斯特拉（Dijkstra）算法是一种用于在图中找到单个源点到其他所有节点的最短路径的算法。这种算法适用于带权重的有向图和无向图，并且假设图中没有负权重的边。迪杰斯特拉算法的基本思想是贪心策略，即每一步都选择当前能够到达的最短路径。

以下是使用Python实现迪杰斯特拉算法的一个简单示例：

import sys

def dijkstra(graph, start):
    # 初始化距离表，所有节点的距离都设置为无穷大
    distances = {vertex: float('infinity') for vertex in graph}
    # 起点到自己的距离为0
    distances[start] = 0
    
    # 未访问的节点集合
    unvisited = set(graph.keys())
    
    while unvisited:
        # 选择一个未访问的最小距离节点
        current_vertex = min(unvisited, key=lambda vertex: distances[vertex])
        # 当前节点的距离已确定，从待访问集合中移除
        unvisited.remove(current_vertex)
        
        # 遍历当前节点的邻居
        for neighbor, weight in graph[current_vertex].items():
            distance = distances[current_vertex] + weight
            # 如果找到更短的路径，则更新距离表
            if distance < distances[neighbor]:
                distances[neighbor] = distance
    
    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}
}

# 计算从起点A到所有节点的最短路径
print(dijkstra(graph, 'A'))

这段代码首先定义了一个`dijkstra`函数，它接收一个图和一个起始点作为参数，返回一个从起始点到所有其他节点的最短路径长度的字典。然后，定义了一个示例图，并调用该函数计算从节点'A'开始的最短路径。