import sys
 
def dijkstra(graph, start):
    # 初始化
    distances = {vertex: sys.maxsize for vertex in graph}  # 记录源点到各顶点的距离
    distances[start] = 0
    visited = set()
    previous_vertices = {vertex: None for vertex in graph}  # 记录最短路径的前驱结点
 
    while graph:
        # 选择当前距离源点最近的未访问顶点
        current_vertex = min(
            {vertex: distances[vertex] for vertex in graph if vertex not in visited},
            key=distances.get
        )
 
        # 标记为已访问
        visited.add(current_vertex)
 
        # 更新当前顶点的相邻顶点的距离
        for neighbor in graph[current_vertex]:
            distance = distances[current_vertex] + graph[current_vertex][neighbor]
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_vertices[neighbor] = current_vertex
 
        # 当前顶点从图中移除
        graph.pop(current_vertex)
 
    return distances, previous_vertices
 
 
# 示例使用
if __name__ == '__main__':
    # 定义图结构（字典表示）
    graph = {
        'A': {'B': 5, 'C': 1},
        'B': {'A': 5, 'C': 2, 'D': 1},
        'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
        'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
        'E': {'C': 8, 'D': 3},
        'F': {'D': 6}
    }
 
    start_vertex = 'A'
    distances, previous_vertices = dijkstra(graph, start_vertex)
 
    # 打印结果
    for vertex in distances:
        path = []
        current_vertex = vertex
        while current_vertex is not None:
            path.insert(0, current_vertex)
            current_vertex = previous_vertices[current_vertex]
        print(f'最短路径: {path}, 最短距离: {distances[vertex]}')