具有优先级队列的Dijkstra (Python)

基础概念

Dijkstra算法是一种用于计算单源最短路径的经典算法。它通过逐步扩展已知最短路径的节点集合，直到找到目标节点的最短路径。优先级队列（Priority Queue）是一种数据结构，用于存储元素并根据优先级进行排序和访问。在Dijkstra算法中，优先级队列用于高效地选择下一个要处理的节点。

类型

优先级队列有多种实现方式，常见的包括：

二叉堆（Binary Heap）：一种基于数组的二叉树结构，插入和删除操作的时间复杂度为O(log n)。
斐波那契堆（Fibonacci Heap）：一种更复杂的堆结构，插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(log n)。

应用场景

Dijkstra算法及其优先级队列实现广泛应用于：

网络路由：计算数据包从源节点到目标节点的最短路径。
地图导航：计算从一个地点到另一个地点的最短路径。
任务调度：根据任务的优先级进行调度。

示例代码（Python）

以下是一个使用二叉堆实现的Dijkstra算法示例：

import heapq

def dijkstra(graph, start):
    queue = []
    heapq.heappush(queue, (0, start))
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous_nodes = {node: None for node in graph}

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        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
                previous_nodes[neighbor] = current_node
                heapq.heappush(queue, (distance, neighbor))

    return distances, previous_nodes

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

distances, previous_nodes = dijkstra(graph, 'A')
print("Distances:", distances)
print("Previous Nodes:", previous_nodes)