什么是Dijkstra算法？

Dijkstra算法是一种用于计算图中单源最短路径的贪心算法。它可以计算从一个源点到其他所有点的最短路径。该算法的基本思想是从源点开始，依次计算出到各个顶点的最短路径，直到计算出到所有顶点的最短路径为止。在计算的过程中，需要维护一个集合S，表示已经求出最短路径的顶点集合，以及一个数组d，表示源点到各个顶点的最短距离。每次从未求出最短路径的顶点中选择一个距离最短的顶点加入集合S，并更新与该顶点相邻的顶点的最短距离。重复这个过程，直到所有顶点都被加入集合S为止。

以下是一个使用Dijkstra算法计算最短路径的Python代码示例：

import heapq

def dijkstra(graph, start):
    # 初始化距离数组
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 初始化堆
    heap = [(0, start)]
    while heap:
        # 弹出距离最小的顶点
        (d, node) = heapq.heappop(heap)
        # 如果该顶点已经求出最短路径，则跳过
        if d > dist[node]:
            continue
        # 更新与该顶点相邻的顶点的最短距离
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist