迪杰斯特拉算法(Dijkstra)算法 python

迪杰斯特拉算法（Dijkstra's algorithm）是一种用于求解单源最短路径问题的算法。它可以找到从一个顶点到其他所有顶点的最短路径。

以下是迪杰斯特拉算法的基本步骤：
1. 创建一个空的距离字典，用于存储每个顶点到起始顶点的距离。将起始顶点的距离设置为0，其他顶点的距离设置为无穷大。
2. 创建一个空的已访问集合，用于存储已经找到最短路径的顶点。
3. 重复以下步骤，直到所有顶点都被访问：
a. 从未访问的顶点中选择距离起始顶点最近的顶点，并将其添加到已访问集合中。
b. 更新与该顶点相邻的顶点的距离。如果通过当前顶点到达相邻顶点的路径比之前计算的路径更短，则更新距离字典中的值。
4. 最终，距离字典中存储了从起始顶点到每个顶点的最短路径。

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

import sys

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

    # 初始化已访问集合
    visited = set()

    while len(visited) < len(graph):
        # 选择距离最小的顶点
        min_distance = sys.maxsize
        min_vertex = None
        for vertex in graph:
            if vertex not in visited and distances[vertex] < min_distance:
                min_distance = distances[vertex]
                min_vertex = vertex

        # 将选中的顶点添加到已访问集合中
        visited.add(min_vertex)

        # 更新与选中顶点相邻的顶点的距离
        for neighbor, weight in graph[min_vertex].items():
            new_distance = distances[min_vertex] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance

    return distances

# 示例图的邻接表表示
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6},
    'D': {'B': 3, 'C': 2, 'E': 4, 'F': 2},
    'E': {'C': 6, 'D': 4, 'F': 6},
    'F': {'D': 2, 'E': 6}
}

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

for vertex, distance in distances.items():
    print(f"从顶点 {start_vertex} 到顶点 {vertex} 的最短距离为 {distance}")

这段代码实现了迪杰斯特拉算法，通过邻接表表示图，并计算从起始顶点到其他顶点的最短距离。你可以根据自己的需求修改图的表示和起始顶点。