Dijkstra算法是一种用于计算单源最短路径的经典算法，适用于加权有向图，其中所有边的权值都为非负数。以下是如何使用Python实现Dijkstra算法的一个简单示例：

import heapq  
def dijkstra(graph, start):  
    # 初始化距离字典，将起点的距离设为0，其余为无限大  
    distances = {vertex: float('infinity') for vertex in graph}  
    distances[start] = 0  
    # 优先队列用于存储待处理的顶点和距离  
    priority_queue = [(0, start)]  
    while priority_queue:  
        # 取出距离最小的顶点  
        current_distance, current_vertex = heapq.heappop(priority_queue)  
        # 如果取出的距离大于已记录的距离，说明这个点已经处理过  
        if current_distance > distances[current_vertex]:  
            continue  
        # 更新当前顶点邻接节点的距离  
        for neighbor, weight in graph[current_vertex].items():  
            distance = current_distance + weight  
            # 发现更短的路径，更新距离字典  
            if distance < distances[neighbor]:  
                distances[neighbor] = distance  
                heapq.heappush(priority_queue, (distance, neighbor))  
    return distances  
# 示例图，用字典的嵌套表示  
example_graph = {  
    'A': {'B': 1, 'C': 4},  
    'B': {'A': 1, 'C': 2, 'D': 5},  
    'C': {'A': 4, 'B': 2, 'D': 1},  
    'D': {'B': 5, 'C': 1}  
}  
# 计算从顶点'A'开始的最短路径  
shortest_paths = dijkstra(example_graph, 'A')  
print(shortest_paths)  

算法解析：

1. 初始化：

   • 创建一个距离字典distances，其中初始化起点的距离为0，其他点的距离为无穷大。
   • 使用优先队列（采用Python的heapq模块）来存储已认知的顶点及其当前最短距离。

2. 循环处理：

   • 每次从队列中提取距离最小的顶点。
   • 对于该顶点的每个邻居，计算从起点经过该顶点到邻居的路径距离。
   • 如果计算出的路径比已知的距离短，则更新距离字典，并将该邻居添加到队列中。

3. 结束条件：

   • 当优先队列为空时，所有可以确定的最短路径已被找到。

这个算法适用于无负权边场景，并在编程竞赛、图论等领域有广泛应用。Dijkstra算法的时间复杂度为O(V^2)（用数组实现）或O((V+E)logV)（用优先队列实现，V是顶点数量，E是边的数量）。