实现Dijkstra最短路径算法

Dijkstra最短路径算法是一种贪心算法，用于求解图中从一个起点到其他所有节点的最短路径。下面是Dijkstra算法的实现过程：

1. 初始化

将起点的距离初始化为0，其他节点的距离初始化为无穷大。

2. 选择最近的节点

从未标记节点中选择一个距离起点最近的节点，标记该节点。

3. 更新距离

对于当前节点的所有邻居节点，计算从起点到该邻居节点的距离，如果该距离小于该邻居节点当前的距离，则更新该邻居节点的距离。

4. 重复步骤2和步骤3，直到所有节点都被标记或者没有未标记节点时停止。

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

import sys

def dijkstra(graph, start):
    # 初始化距离
    dist = {node: sys.maxsize for node in graph}
    dist[start] = 0

    # 标记节点
    visited = set()

    while len(visited) != len(graph):
        # 选择最近的节点
        curr_node = min((node, dist[node]) for node in graph if node not in visited)[0][0]
        visited.add(curr_node)

        # 更新距离
        for neighbor, weight in graph[curr_node].items():
            new_dist = dist[curr_node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist

    return dist

其中，graph是一个邻接表，表示图的结构和边的权重。start是起点节点。函数返回一个字典，表示从起点到各个节点的最短距离。