最短路径（迪杰斯特拉算法）

迪杰斯特拉算法是一种用于解决带权图的单源最短路径问题的贪心算法。该算法的基本思想是从起点开始，逐步扩大到其他节点，直到到达终点。在扩展的过程中，每次选择当前距离起点最近的一个节点进行扩展，直到扩展到终点为止。该算法的时间复杂度为O(n^2)，其中n为节点数。

以下是Python实现Dijkstra算法的代码示例：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    
    # 初始化堆
    heap = [(0, start)]
    
    while heap:
        # 弹出堆中距离起点最近的节点
        (distance, node) = heapq.heappop(heap)
        
        # 如果当前节点已经被访问过，则跳过
        if distance > dist[node]:
            continue
        
        # 遍历当前节点的邻居节点
        for neighbor, weight in graph[node].items():
            # 计算到邻居节点的距离
            new_distance = dist[node] + weight
            
            # 如果新的距离比之前的距离更短，则更新距离字典和堆
            if new_distance < dist[neighbor]:
                dist[neighbor] = new_distance
                heapq.heappush(heap, (new_distance, neighbor))
    
    return dist