dijkstras算法

Dijkstra算法是一种用于解决带权图的单源最短路径问题的贪心算法。它通过维护一个距离起点的距离数组和一个已访问节点的集合来工作。算法的基本思想是从起点开始，每次选择距离起点最近的一个节点，然后以该节点为中心进行扩展，更新与其相邻节点的距离。重复这个过程直到所有节点都被访问过。

以下是Dijkstra算法的Python实现：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        (current_distance, current_node) = heapq.heappop(heap)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

其中，graph是一个字典，表示图的邻接表，start是起点。函数返回一个字典，表示每个节点到起点的最短距离。