python图的最短路径Dijkastra

好的，Dijkstra算法是解决带权有向图或无向图的单源最短路径问题的一种算法。其基本思想是：将图分成两个部分，已确定最短路径的顶点集合P和未确定最短路径的顶点集合Q。初始时，集合P为空，集合Q包含所有顶点。然后，从集合Q中选取一个距离源点最近的顶点u加入到集合P中，并考虑通过u更新其它顶点到源点的距离。重复这个过程，直到所有顶点都被加入到集合P中。

下面是Dijkstra算法的Python代码实现：

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    pq = [(0, start)]
    while pq:
        (cost, curr) = heapq.heappop(pq)
        if cost > dist[curr]:
            continue
        for neighbor, weight in graph[curr].items():
            new_cost = dist[curr] + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))
    return dist

其中，graph表示图的邻接表，start表示起点。返回值为一个字典，表示每个顶点到起点的最短距离。