Dijkstra算法代码

Dijkstra算法是一种用于求解最短路径的算法，它可以计算出从一个起点到其他所有节点的最短路径。下面是Dijkstra算法的伪代码：

1. 创建一个集合S，表示已经找到最短路径的节点集合，初始化为空。
2. 创建一个数组dist，表示起点到各个节点的最短距离，初始化为无穷大。
3. 将起点加入集合S中，设置起点的dist为0。
4. 对于起点的所有邻居节点，更新它们的dist值，即如果从起点到该邻居节点的距离小于该节点原有的dist值，则更新为较小的距离。
5. 从未加入集合S的节点中，选择dist值最小的节点加入集合S中，重复步骤4和5，直到所有节点都加入了集合S为止。

下面是Dijkstra算法的Python代码实现：

def dijkstra(graph, start):
    S = set()
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    while len(S) < len(graph):
        node = min(graph, key=lambda x: dist[x] if x not in S else float('inf'))
        S.add(node)
        for neighbor in graph[node]:
            if neighbor not in S:
                new_dist = dist[node] + graph[node][neighbor]
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist

    return dist