堆优化的Dijkstra算法的原理与实现

Dijkstra算法是一种用于求解单源最短路径问题的经典算法，它的主要思想是从源点开始，逐步扩展最短路径集合，直到到达目标节点。堆优化的Dijkstra算法是对传统Dijkstra算法的一种优化，通过使用优先队列（通常使用最小堆实现）来维护当前已经确定的最短路径集合，从而提高算法的效率。

下面将介绍堆优化的Dijkstra算法的原理与实现，并给出一个使用例子。

1. 算法原理：

- 初始化：创建一个优先队列，用于存放当前确认的最短路径集合，以及一个距离表dist，用于存放每个节点到源点的当前最短距离。将源点加入到优先队列，并将dist表中源点的距离设置为0。

- 迭代：每次从优先队列中取出距离最小的节点u，将其加入到已确认的最短路径集合中。然后遍历节点u的所有邻接节点v，更新节点v到源点的距离，即若dist[u]+w(u,v)<dist[v]，则更新dist[v]=dist[u]+w(u,v)，并将节点v加入到优先队列中。

- 重复上述步骤，直到优先队列为空或者目标节点已被加入到已确认的最短路径集合中。

2. 算法实现:

import heapq

def dijkstra(graph, source):
    # 初始化
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    pq = [(0, source)]  # 优先队列，用于存放当前确认的最短路径集合
    while pq:
        # 取出距离最小的节点
        curr_dist, curr_node = heapq.heappop(pq)
        if curr_dist > dist[curr_node]:
            continue
        # 遍历邻接节点
        for neighbor, weight in graph[curr_node].items():
            new_dist = dist[curr_node] + weight
            # 更新最短距离
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                # 将邻接节点加入优先队列
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

3. 使用例子：

假设有如下有向带权图：

graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'D': 4},
    'C': {'B': 1, 'D': 2},
    'D': {'E': 3},
    'E': {}
}

源节点为A，目标节点为E，现在使用堆优化的Dijkstra算法求解从节点A到节点E的最短路径：

result = dijkstra(graph, 'A')
print(result)

输出结果为：

{'A': 0, 'B': 3, 'C': 2, 'D': 4, 'E': 7}

说明从节点A到节点E的最短路径距离为7，路径为A->C->D->E。