Python 实现迪杰斯特拉算法：使用距离列表求解最短路径

以下是使用距离列表实现迪杰斯特拉算法的 Python 代码：/n/npython/ndef dijkstra(graph, start):/n # 初始化距离列表/n distances = {node: float('inf') for node in graph}/n # 将起点距离设为0/n distances[start] = 0/n # 定义一个集合用于存储已确定最短路径的节点/n visited = set()/n # 循环直到所有节点都被遍历/n while len(visited) != len(graph):/n # 选择距离起点最近的节点/n current_node = min(distances, key=distances.get)/n # 将该节点标记为已访问/n visited.add(current_node)/n # 更新与该节点相邻的节点的距离/n for neighbor in graph[current_node]:/n if neighbor not in visited:/n new_distance = distances[current_node] + graph[current_node][neighbor]/n if new_distance < distances[neighbor]:/n distances[neighbor] = new_distance/n # 从距离列表中删除已访问的节点/n del distances[current_node]/n return visited/n/n/n其中，graph是一个字典，表示图的邻接表，键为节点，值为一个字典，表示该节点与相邻节点之间的边及其权重。例如：/n/npython/ngraph = {/n 'A': {'B': 2, 'C': 1},/n 'B': {'A': 2, 'D': 3, 'E': 2},/n 'C': {'A': 1, 'F': 3},/n 'D': {'B': 3},/n 'E': {'B': 2, 'F': 1},/n 'F': {'C': 3, 'E': 1}/n}/n/n/n表示如下图所示的无向加权图：/n/n/n 2 3/nB----D E/n|// / // /|/n| // // / |/n| // / |/n|/ // / |/nA----C F/n 1 3/n/n/nstart是起点节点的名称，例如'A'。函数返回一个集合，包含所有已访问的节点。在本例中，如果起点为'A'，则返回{'A', 'B', 'C', 'E', 'F', 'D'}。