优先队列优化dijkstra算法

优先队列优化Dijkstra算法是一种基于Dijkstra算法的改进算法，用于解决单源最短路径问题。相比于普通的Dijkstra算法，优先队列优化Dijkstra算法在松弛所有点的过程中，使用了优先队列来存储待松弛的点，从而减少了时间复杂度。

以下是优先队列优化Dijkstra算法的步骤：

1. 初始化：将起点s加入优先队列，距离dis[s]设为0，其他点的距离dis[i]设为正无穷大。
2. 取出优先队列中距离最小的点u，如果u已经被访问过，则跳过该点。
3. 对于u的每个邻接点v，如果dis[u]+w(u,v)<dis[v]，则更新dis[v]的值，并将v加入优先队列。
4. 重复步骤2和3，直到优先队列为空。

以下是优先队列优化Dijkstra算法的代码模板：

import heapq

def dijkstra(graph, start):
    pq = [(0, start)]
    visited = set()
    distances = {start: 0}
    while pq:
        (cost, u) = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u].items():
            if v in visited:
                continue
            if v not in distances or cost + w < distances[v]:
                distances[v] = cost + w
                heapq.heappush(pq, (distances[v], v))
    return distances